Problems & Puzzles: Puzzles

Puzzle 737. Maximize  log(s) / log(maxPrimeFactor(s))

Fred Schneider sent the following nice puzzle:

Maximize  log(s) / log(maxPrimeFactor(s)) where s = sigma(p^x), p is prime and  x >=2

Consider the prime number: 10889273

10889273^5 is interesting with respect to its sigma (or divisor sum)

Let s = sigma(10889273^5)  = 153106796458831178584646446634328654

s is quite smooth for a largish number, 373-smooth in fact.

factor(sigma(10889273^5)) = 
2 * 3^2 * 7 * 11^2 * 19^3 * 53 * 73 * 109 * 163 * 181 * 211 * 223 * 229 * 283 * 307 * 337 * 373

If we take the log(s) / log(maxPrimeFactor(s)) = log(s) / log(373, we get 13.6816 roughly.

Q. Can you find a higher ratio of log(s) / log(maxPrimeFactor(s)) where s = sigma(p^x), p is a prime, and x >=2 and give some insight into how you found the solution?

(Note: x=1 is not for consideration because it's relatively simple to create find a 3-smooth sigma(p) )

Contributions came from Jaroslaw Wroblewski, Jan van Delden and Vicente Felipe Izquierdo.


Wroblewski wrote:

Regarding Puzzle 737, the ratio can be arbitrarily large.

For any x the polynomial sigma(p^x)=1+p+p^2+...+p^x=(p^(x+1)-1)/(p-1)
in variable p splits into factors of degree at most EulerPhi[x+1]. In
the worse scenario those factors are primes and even in such a case
the ratio tends to x/EulerPhi[x+1] as p goes to infinity. Since the
ratio x/EulerPhi[x+1] can be arbitrarily large, so can be the ratio
given in the puzzle.

Unfortunately the above proof does not produce any example small
enough to leave hope for factoring sigma(p^x).


Jan wrote:

We have sigma(p^a)=(p^(a+1)-1)/(p-1).
The polynom x^a-1 is divisible by x^b-1 if b|a.
For instance x^6-1 is divisible by x-1,x^2-1 and x^3-1.
Giving x^6-1/(x-1)=(x+1)(x^2+x+1)(x^2-x+1)=Phi(2).Phi(3).Phi(6)
[For more information look up: Cyclotomic polynomials]
If these factors don't split upon substitution of a prime p, the worst that can happen is that
f=max(log(s))/log(maxPrimeFactor(s))=log(p^5)/log(p^2)=2.5 (if a=5) approximately.
This minimum could be increased by increasing a. It could therefore be wise to choose a+1
equal to a product of small primes, forcing the highest power of x to be small compared to a.
-x+1). Here we would have a minimum f=log(p^29)/log(p^8)=3.625.
However now we have more factors which simultaneously have to split upon substituting a prime
p. Which might be too much to ask for.
The found value of 13.68 is huge in the sense that it tells us that (x+1) splits into at least
3 primefactors and 6 primefactors for the other two terms (if the primefactors are about
the same size..).
In fact we have, for x=10889273:
x+1=                (2 or 1 mod 2,i.e. empty statement)
x^2-x+1= (3 or 1 mod 6)
x^2+x+1=     (3 or 1 mod 6)
My routine uses these polynomial splits combined with trial division given a list of
primes<=B, where B depends on p,a and the current maximum value of the constant f. I used
B=trunc(p^(a/f)). I didn't use the above "mod" relations. If a/f>1, the primelist will
increase in size rather fast. To save memory capacity one could either search for f at least 
equal to a and hope for the best, or factorise s instead.
a   p                                q     f                     upb(p)
2   1389087499          157    8.327092355  265.10^7
5   10889273              373  13.68156225   125.10^7
11  19658641     1234687  13.17053917   477.10^5


Vicente wrote:

Un punto de partida donde se pueden encontrar valores muy grandes para la solución pedida sería el caso donde:
p^k = (2r+1)^s
Donde 2r+1 debe ser mínimo.
O  sea, sería encontrar la potencia de un primo que equivalga a la potencia de un impar pequeño.
En este caso sigma(p^k) sería máximo respecto a 2r+1.


Records   |  Conjectures  |  Problems  |  Puzzles