Euler Projesi 248. Soru

Euler totient fonksiyon değeri 13! olan sayılar

$\phi $(n)=13! olacak şekilde ilk n sayısı 6227180929 dur.

Böylesi 150.000'ıncı sayıyı bulunuz.

[Project Euler]

Cevap: 23507044290

PYTHON from numutil import is_prime, divisors # TODO check for duplicates def inverse_phi(N, a=1): saved = [] if N < 1: raise ValueError if N == 1: if a > 1: return [1] return [1, 2] for div in divisors(N): if (div < a) or (not is_prime(div + 1)): continue N_ = N / div div += 1 P = div while True: saved += map(lambda x: x*P, inverse_phi(N_, div)) if N_ % div: break P *= div N_ /= div return saved def euler248(): ret = inverse_phi(1*2*3*4*5*6*7*8*9*10*11*12*13) ret = list(ret) ret.sort() return ret[100000-1] print euler248() C,C++: #include <iostream> #include <queue> #include <cmath> #include <set> using namespace std; long long pp(long long a, int b) { long long ret = 1; for (int i=0; i<b; i++) ret *= a; return ret; } bool isprime(long long x) { if (x==1) return false; if (x%2==0) return x==2; for (long long y=3; y*y<=x; y+=2) if (x%y==0) return false; return true; } vector<long long> primes; vector<long long> res; void solve(int top, long long cur, long long rem) { if (rem==1) res.push_back(cur); for (int i=top-1; i>=0; i--) { long long p = primes[i]; if (rem%(p-1)!=0) continue; solve(i,cur*p,rem/(p-1)); long long trem = rem/(p-1); long long tcur = cur*p; while (trem%p==0) { trem/=p; tcur*=p; solve(i,tcur,trem); } } } int main() { for (int i=0; i<=10; i++) for (int j=0; j<=5; j++) for (int k=0; k<=2; k++) for (int l=0; l<=1; l++) for (int m=0; m<=1; m++) for (int n=0; n<=1; n++) { long long num = pp(2,i)*pp(3,j)*pp(5,k)*pp(7,l)*pp(11,m)*pp(13,n); if (isprime(num+1)) {primes.push_back(num+1);} } sort(primes.begin(),primes.end()); res.clear(); solve(primes.size(),1,6227020800LL); sort(res.begin(),res.end()); printf("%I64d\n",res[99999]); system("PAUSE"); } C#: static void Euler248() { MathExtPNF.initMathExtPrimes(1000000); MathExtPNF.initPhiTable(); uint N = 13; //uint N = 5; ulong NFirst5 = 1; ulong NFirst13 = 6227180929; ulong Nfac = MathExt.factoriell(N); //E248_tryFind(NFirst5, Nfac, 17); C.WriteLine("-------------------------------"); // we just accept primefactors up to 13. E248_Base = new ulong[] { 2, 3, 5, 7, 11, 13 }; // here we have a table which tells us how many times each of this primefactors occur. uint[] lFactors = new uint[] { 0, 0, 0, 0, 0, 0 }; // factorize N! and build list ulong lTst = Nfac; for (uint i = 0; i < 6; i++) { ulong lChk = E248_Base[i]; while (lTst % lChk == 0) { lFactors[i]++; lTst /= lChk; } } // Collection of all solutions. E248_List = new SortedDictionary<ulong, bool>(); //C.WriteLine("First Element should be 6227180929"); C.WriteLine(E248_make_val(lFactors) + " has to be " + MathExt.factoriell(N)); // start the solution finding process E248_chk(lFactors, 1,1); C.WriteLine("NumberOfSolutions:"+E248_List.Count()); C.WriteLine("First Solution:"+E248_List.ElementAt(0)); if (E248_List.Count() > 100000) C.WriteLine(E248_List.ElementAt(99999)); else { foreach (ulong lSol in E248_List.Keys) { C.WriteLine(lSol + "=" + MathExtPNF.factorizeAsString(lSol)); } } } // helper routine for small values of N. Search for pCnt values with // phi(value)=pRes. starting with pFirst. // uses my mathExtensions to calculate phi. static void E248_tryFind(ulong pFirst,ulong pRes,ulong pCnt) { ulong i = pFirst; for (ulong lCnt = 0; lCnt < pCnt; i++) { if (MathExtPNF.eulers_phi(i) == pRes) { C.WriteLine(i + "=" + MathExtPNF.factorizeAsString(i)); lCnt++; } } } // prime base values for factorization of N! static ulong[] E248_Base; // collection of solution. static SortedDictionary<ulong,bool> E248_List; // translate table (i0,i1,i2,i3,i4,i5) --> 2**i0 * 3**i1 ... // (bases from E248_Base). static ulong E248_make_val(uint[] pFact) { ulong lRes = 1; for (uint j = 0; j < 6; j++) { lRes *= (ulong)Math.Pow(E248_Base[j], pFact[j]); } return lRes; } // check if table == 0 (i0,i1,...)==(0,0,0..0) by adding all the // (non-negative) values in the pFact table and check Sum against 0. static bool E248_isSolution(uint[] pFact) { uint lSum = 0; for (uint j = 0; j < 6; j++) lSum += pFact[j]; if (lSum == 0) return true; return false; } // Solution handling routine. // when the current table of unused prime factors of 13! is empty (isSolution is true) // then we take the selected Value pVal. // e.q. let N=5, 5!=(3,1,1,0,0,0). // first selected value is (2,1,0,0,0,0)=2**2 * 3**1 = 12 = d1 // 2nd selected value is (1,0,1,0,0,0)=2**1 * 5**1 = 10 = d2 // then d1+1 and d1+1 are both prime // and so we have pVal=13*11 the first value with phi(n)=5! // pVal is the possible solution. static bool E248_add_Solution(uint[] pFact, ulong pVal) { if (E248_isSolution(pFact)) { //if (!E248_List.Keys.Contains(pVal)) // E248_List.Add(pVal, false); try { E248_List.Add(pVal, false); } catch (Exception lEx) { } // when pVal is an odd solution, then 2*pVal is also a solution. // phi(2*l) == phi(2)*phi(l) == phi(l) // sample : phi(61*3)=phi(61*3*2)=5! if (pVal % 2 != 0) { pVal *= 2; //if (!E248_List.Keys.Contains(pVal)) // E248_List.Add(pVal, false); try { E248_List.Add(pVal, false); } catch (Exception lEx) { } } // just for fun to see the progress in finding solutions. if (E248_List.Count % 1000 == 0) C.WriteLine(E248_List.Count); // we found a solution -> no need to recheck the pFact table return true; } // there are still some unused elements in pFact and so pVal is not a solution up to now. // we have to combine pVal with the elements in pFact. return false; } // the main search routine for factors of N!. // pFact are the exponents still useable, pVal is the intermediate solution, pLastTerm // is the last Term found (this is an optimization to avoid double generation of all solutions. static bool E248_chk(uint[] pFact, ulong pVal, ulong pLastTerm) { uint[] lTmp = new uint[6]; for (uint i1 = 0; i1 <= pFact[0]; i1++) { pFact[0] -= i1; lTmp[0] = i1; for (uint i2 = 0; i2 <= pFact[1]; i2++) { pFact[1] -= i2; lTmp[1] = i2; for (uint i3 = 0; i3 <= pFact[2]; i3++) { pFact[2] -= i3; lTmp[2] = i3; for (uint i4 = 0; i4 <= pFact[3]; i4++) { pFact[3] -= i4; lTmp[3] = i4; for (uint i5 = 0; i5 <= pFact[4]; i5++) { pFact[4] -= i5; lTmp[4] = i5; for (uint i6 = 0; i6 <= pFact[5]; i6++) { pFact[5] -= i6; lTmp[5] = i6; // when not all exponents selected are 0. if (i1 + i2 + i3 + i4 + i5 + i6 > 0) { ulong lNewTerm = E248_make_val(lTmp); // ideen : wir brauchen values mit phi(x)==l // wenn l+1 prim ist, dann ist phi(l+1)==l // aber : wenn l==2 ist, dann ist auch phi(2*2)==l ! // aber das funktioniert nur, wenn pVal noch nicht == 0(2) ist. // noch ein scenario : wenn pVal bereits == 0(l) ist, dann // liefert phi(l) nicht l-1 sondern l. // if the value is not already part of pVal (n=p*q) lNewTerm++; if ((pVal % lNewTerm) != 0) { if (MathExtPNF.isPrime2(lNewTerm)) { ulong lValNew = lNewTerm * pVal; if (!E248_add_Solution(pFact, lValNew)) if (lNewTerm >= pLastTerm) E248_chk(pFact, lValNew, lNewTerm); } } lNewTerm--; // when pVal is odd and l==2, there phi(2+1=3)==2 (already handled above), but // also phi(4)==2 ! // x==1(2) then phi(4x)==2*phi(x) // sample phi(61*3)==phi(61*4)=60*2=120=5! if ((lNewTerm == 2) && ((pVal % 2 != 0))) { ulong lValNew = 4 * pVal; if (!E248_add_Solution(pFact, lValNew)) if (lNewTerm >= pLastTerm) E248_chk(pFact, lValNew,lNewTerm); } // one more possible case. when pVal == 0(l) then phi(l) will give a factor of l // instead of the expected l-1. but this is no problem, when l is also prime. // sample : N=5 (we search for factors of 5!). // 5! = (3,1,1). the first value we select is (1,1,0) [6] and the 2nd value we select is // (2,0,0) [4]. (6+1=7 (prime) and 4+1=5 (prime)). // pVal = 7*5. // now the last selected value is (0,0,1) [5]. // now pVal is already == 0(5) and 5 is prime so we generate // pBalNew=7*5*5 and phi(pValNew)=5! if ((pVal % lNewTerm) == 0) { if (MathExtPNF.isPrime2(lNewTerm)) { ulong lValNew = lNewTerm * pVal; if (!E248_add_Solution(pFact, lValNew)) if (lNewTerm >= pLastTerm) E248_chk(pFact, lValNew,lNewTerm); } } } pFact[5] += i6; } pFact[4] += i5; } pFact[3] += i4; } pFact[2] += i3; } pFact[1] += i2; } pFact[0] += i1; } return false; }