Sums of prime powers

[grandpascorpion]

Originally Posted by m_f_h

I don't know if I belong to the folks, but I don't store anything ; your algorithm is based on mine with my idea of iteratively decreasing the upper limit of the second prime p_j (by taking the floor of the sum to 1/e_j) and increasing the lower limit of its exponent e_j (by taking th ceiling of the exponent corresponding to value of p_j).
The difference is that you compare each time if the sums are equal while I only compare it when p_j and e_j didn't change w.r.t. the previous iteration, and you make primality tests which take useless time.

(and, my function restricts the search to a sum in [A,B] by taking the exponent e_i of the first prime p_i only in a certain range, condition which you can drop if you wish.)

PS: I don't mean to be aggressive, somehow my style sometimes might let think the contrary, but its really not intended!

No worries. Sorry, I misread your bit. I thought you were storing data.
Also, my algorithm isn't based on yours intentionally.

The bottom line though is how long our scripts take to run.
It's true I haven't optimized my code regarding the psuedoprime but
it takes 20ms for me to check through 10^6. It takes you 10 seconds, which is 500 times slower. Sorry, if you have improved on this time.

No offense intended here.

[ATH]

However, is it logical to check e.g. a prime on 1e4..1e5 up to a sum of 10^100 without checking primes 1e5..1e6 first ? You might well have 1+nextprime(10e5) equal to the sum corresponding to a big power of some small prime ? But well... provided you allow in your function to resume where a previous search has ended, there's not a big difference (and your results sound more spectacular)

Well, for p1=2 it has to check to exponent 332 but allready after 46 sec at p1=10^5 it only needs to check up to exponent 20. I guess I made it this way because Patrick123 made it like this and it made sense to me, and this way it checks a mixture of small and large values for solutions.

Now I ran the program up to p1=8*10^6 and S=10^100 for each p1, still no other solution.

[grandpascorpion]

I found one simple way to speed up my program.
I completed an exhaustive search through 10^36. It took about 1 hour to run.

For primes p1 and p2 > 2, if (p1^(x1+1)-1)/(p1-1) = (p2^(x2+1)-1)/(p1-1)
then x1 = x2 (mod 2). Otherwise, one sum will be even, the other odd.

So, the upshot is that only primes through n^(1/4) need to be checked , instead of n^(1/3), because 3 != 2 (mod 2).

[mfgoode]

Originally Posted by m_f_h

I don't see how this is related to the search of two pairs (p,e) which give the same value for s(p,e) = sum( p^k, k=0...e).

Sorry m_f_h it is not related.

Originally Posted by mfgoode

I dont understand the various algorithms presented as Im not into programming.

But if it will be of some help to elucidate, *not necessarily this problem,* but its a good general rule to bear in mind.

What Patrick 123 has worked out is correct and those are the only numbers found so far up to date [ref: Wells]

Also the conjecture that if the power of a Mersenne prime is itself a Mersenne prime is countered by the M-prime 8191 which is a counter example.

Mally

[m_f_h]

Originally Posted by mfgoode

Sorry m_f_h it is not related.

What Patrick 123 has worked out is correct and those are the only numbers found so far up to date [ref: Wells]

Also the conjecture that if the power of a Mersenne prime is itself a Mersenne prime is countered by the M-prime 8191 which is a counter example.

This gives you already a power-ful comfortable 2-rounds-ahead advantage w.r.t. any other candidate for the international "confusing through unrelated facts" contest: you may slow down and relax now .

PS: or, provide a power-ful counter-proof for the Catalan series primality conjecture: M2=3, M3=7, M7=127, M127=... all prime, M(M127) prime ?

[mfgoode]

Originally Posted by m_f_h

This gives you already a power-ful comfortable 2-rounds-ahead advantage w.r.t. any other candidate for the international "confusing through unrelated facts" contest: you may slow down and relax now .

PS: or, provide a power-ful counter-proof for the Catalan series primality conjecture: M2=3, M3=7, M7=127, M127=... all prime, M(M127) prime ?

Thank you m_f_h for the advantage.

I was just adding my two cent bit!

At present I am trying to crack out C_5 where C_n+1 = 2^C_n+1 -1 on a super computer as C_5 has more than 10^37 digits

Thanks to you again as I learnt what a Catalan number is!

Mally

[Pascal Ochem]

Originally Posted by grandpascorpion

I found one simple way to speed up my program.
I completed an exhaustive search through 10^36. It took about 1 hour to run.

For primes p1 and p2 > 2, if (p1^(x1+1)-1)/(p1-1) = (p2^(x2+1)-1)/(p1-1)
then x1 = x2 (mod 2). Otherwise, one sum will be even, the other odd.

So, the upshot is that only primes through n^(1/4) need to be checked , instead of n^(1/3), because 3 != 2 (mod 2).

Also, for odd primes x and y, x^4+x^3+x^2+x+1 = y^2+y+1 has no solution since
y := x^2+(x-1)/2 is too small and y := x^2+(x+1)/2 is too big.

This should mean that only primes through n^(1/5) need to be checked.

[grandpascorpion]

Ah, great point. There's probably similar cases that can be removed from consideration.

For instance, there's no answer for

(x^9-1)/(x-1) = (y^5-1)/(y-1)

because y = (x^2+floor(x/4)) is too low and y = (x^2+floor(x/4) +1) is too high

[Pascal Ochem]

for primes x, y > 3, we also have
(x^9-1)/(x-1) = 0 (mod 3) whereas (y^5-1)/(y-1) != 0 (mod 3)

[grandpascorpion]

Yes and on that note:

For primes x, y > 3, in order to find an answer to: (x^(m+1)-1)/(x-1) = (y^(k+1)-1)/(y-1), you must have both sides be have the same remainder when divided by 3 of course.

If x= 6n+1, you only need to check k=m-6s where s> 1

Similarly, by checking other mods you can further pare down the searching.

[grandpascorpion]

for primes x, y > 3, we also have
(x^9-1)/(x-1) = 0 (mod 3) whereas (y^5-1)/(y-1) != 0 (mod 3)

Sorry, I affirmed your statement before but it's not correct:

If x=y=2 (mod 3), (x^9-1)/(x-1) = (y^5-1)/(y-1) = 1 (mod 3)

Example x=5, y=11: (5^9-1)/(5-1) = (11^5-1)/(11-1) = 1 (mod 3)

=============================================

Also,if for (x^(m+1)-1)/(x-1) = (y^(k+1)-1)/(y-1),

and m=5, k=3 the only possible solutions are for x=5b+3,4 and x = 11c + 1,2,7,10