mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-06-25, 17:40   #12
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

CC416 Posts
Default

Quote:
Originally Posted by bsquared View Post
Code:
>> x=2^7* 5 * 23 * 127 * 659 * 53323 * 1876187 * 97544836889 * 665320793909
7998766649128898059663516612687535453720960
>> totient(x)
3031634148236289733373855928919180891127808
>> sigma(x,1)-x
12142697391577851168337274092012830083559040
>>
What program gave you totient() and sigma() functions? I expected YAFU from the ">>" prompts, but my YAFU doesn't like them.
EdH is online now   Reply With Quote
Old 2020-06-25, 19:21   #13
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×32×7×13 Posts
Default

It is yafu starting from a r381 (wip-branch).
bsquared is offline   Reply With Quote
Old 2020-06-25, 19:31   #14
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

22·19·43 Posts
Default

Quote:
Originally Posted by bsquared View Post
It is yafu starting from a r381 (wip-branch).
Of course! The two machines I checked were only at 380!

Thanks!
EdH is online now   Reply With Quote
Old 2020-06-25, 19:38   #15
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

31 Posts
Default

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
@Dieter: The solution doesn't have prime factors > 2^64.
yae9911 is offline   Reply With Quote
Old 2020-06-26, 12:28   #16
Dieter
 
Oct 2017

5016 Posts
Default

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.
Dieter is offline   Reply With Quote
Old 2020-07-05, 22:21   #17
uau
 
Jan 2017

73 Posts
Default

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 = p-1
    if n % e == 0:
        used.add(p)
        rec(n//e//p**i, target, used, res*p**(i+1), divsum*((p**(i+2)-1)//(p-1)))
        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)
Given the number of smaller relative primes, RP=3031634148236289733373855928919180891127808, the program
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 (p-1)p^(i-1) in RP, it follows that (p-1) 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 (p-1)p^(i-1) 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.
uau is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
June 2019 Xyzzy Puzzles 5 2019-06-03 05:54
June 2018 Batalov Puzzles 8 2018-07-04 06:45
June 2017 R. Gerbicz Puzzles 14 2017-07-03 20:01
June 2016 Xyzzy Puzzles 16 2016-07-07 02:51
June 2015 Batalov Puzzles 10 2015-07-07 14:59

All times are UTC. The time now is 15:36.

Wed Aug 12 15:36:54 UTC 2020 up 26 days, 11:23, 2 users, load averages: 1.73, 2.05, 2.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.