20200625, 17:40  #12 
"Ed Hall"
Dec 2009
Adirondack Mtns
3543_{10} Posts 
What program gave you totient() and sigma() functions? I expected YAFU from the ">>" prompts, but my YAFU doesn't like them.

20200625, 19:21  #13 
"Ben"
Feb 2007
3,361 Posts 
It is yafu starting from a r381 (wipbranch).

20200625, 19:31  #14 
"Ed Hall"
Dec 2009
Adirondack Mtns
3×1,181 Posts 

20200625, 19:38  #15 
"Hugo"
Jul 2019
Germany
31 Posts 
PARI/GP confirms
Code:
x=2^7* 5 * 23 * 127 * 659 * 53323 * 1876187 * 97544836889 * 665320793909 %111 = 7998766649128898059663516612687535453720960 (21:22) gp > eulerphi(x) %112 = 3031634148236289733373855928919180891127808 (21:22) gp > sigma(x)x %113 = 12142697391577851168337274092012830083559040 
20200626, 12:28  #16 
Oct 2017
143_{8} Posts 
Thank you for the confirmations!
@yae9911: Thank you. Otherwise I would have given up. It is a critical point, if a number fits into one register or not. 
20200705, 22:21  #17 
Jan 2017
2·43 Posts 
Here's the program I used:
Code:
#!/usr/bin/python3 from gmpy2 import is_prime def rec(n, target, used=set(), res=1, divsum=1, last1=None, last2=None): if n == 1: if divsum  res == target: print(res) if 2 not in used and divsum * 3  2*res == target: print(2*res) return p, i = divs[n] e = p1 if n % e == 0: used.add(p) rec(n//e//p**i, target, used, res*p**(i+1), divsum*((p**(i+2)1)//(p1))) used.remove(p) r = n // p for k in divisors(r): if p == last1 and k >= last2: continue t = k*p + 1 if t in primes and t not in used: rec(r//k, target, used, res*t, divsum*(t+1), p, k) factors = [(2, 18), (3, 3), (7, 2), (11, 1), (13, 1), (47, 1), (3169, 1), (8887, 1), (66643, 1), (72161, 1), (2495839, 1), (3847619, 1)] target = 12142680281284711468101282998309016699980172 divs = {1:None} for p, i in factors: prev = list(divs.keys()) for j in range(1, i+1): pp = p ** j for d in prev: divs[d * pp] = (p, j) def divisors(n, divs=divs): if n == 1: yield 1 return p, i = divs[n] pows = [1] for j in range(i): pows.append(pows[1]*p) for d in divisors(n // pows[1]): for m in pows: yield d * m primes = set(d+1 for d in divs if is_prime(d+1)) rec(max(divs), target) finds all possible numbers for which euler_phi(n) equals this given value, and checks whether the divisor sum has the desired property. Since each prime power factor p^i in n produces a factor of (p1)p^(i1) in RP, it follows that (p1) divides RP, and p is of the form d+1 for some divisor d or RP. This limits the set of primes possibly appearing in n to that set. Thus the problem essentially becomes a packing problem  find a subset of powers of those primes such that the factors of (p1)p^(i1) add up to match exactly those in RP. The program iterates through possible solutions by trying different ways to select a prime power for n that reduces or eliminates the largest remaining prime factor in RP, then recursively solving the remaining values. There are two separate cases  eliminating a factor p with p^i with i > 1 (under "if n% e == 0:") and eliminating it a single larger prime of the form k*p+1. The "used" set is needed to avoid a case like 3^2 being used to eliminate a factor of 3 from RP, then trying to use 3 again to eliminate a factor of 2. The program is careful to avoid repeating work by trying the same solution again. It won't try both selecting 2 and then 3, and later 3 then then 2. Eliminating a factor p with a power p^i with i > 1 always eliminates all the remaining powers of p, so it'll always be the last operation for that prime. The "last1" and "last2" arguments are used to ensure that factors removing same prime are in decreasing order  to eliminate powers of 2, adding 5 then 3 is allowed, but not vice versa. The divisor sum is also calculated recursively, as it can also be expressed as a product of independent terms from each p^i factor in n. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
June 2019  Xyzzy  Puzzles  5  20190603 05:54 
June 2018  Batalov  Puzzles  8  20180704 06:45 
June 2017  R. Gerbicz  Puzzles  14  20170703 20:01 
June 2016  Xyzzy  Puzzles  16  20160707 02:51 
June 2015  Batalov  Puzzles  10  20150707 14:59 