[seqfan] A078467: Proof of a(34) = 622699582951

Hagen von EItzen math at von-eitzen.de
Mon Jun 8 18:48:02 CEST 2009


Hello seqfans,

in 2007, Joe K. Crump showed that a(34) <= 622699582951 in sequence A078467.
I now have determined that equality holds: a(34) = 622699582951.

However, since adding this entry should change the b-file as originally 
submitted by J._C. Schlage-Puchta (the line "34 -1" (for "unknown") 
should be changed to "34 622699582951"), I am unsure how to best submit 
the change.

Hagen

P.S: Here's an outline about what I (or mostly my computer) did:
Assume  3^n = 34 mod n  for some n < 622699582951.
Then n must not be divisible by 2,3,17 (1^n = 0 mod2, 0^n = 1 mod 3, 3^n 
= 0 mod 17 have no solutions)
and must be composite (since 3^p = 3 mod p for prime p -- this by itself 
does not rule out n=31, but the exact definition of A078467 does).
If r is a natural number, we can exclude that r divides n by the 
following algorithm:
1) Determine for which x we have (3^r)^x = 34 mod r. (If r is prime, 
this simplifies to 3^x=34 mod r). Either no solution exists; or the 
exact condition will be that x = b mod c for some numbers 0<=b<c and c 
dividing phi(r).
2) If no solution exists, clearly r cannot be a divisor of n and we are 
done.
3) If gcd(b,c,2*3*17)>1, then r cannot be a divisor of n and we are done.
4) In all other cases try all numbers m=r*(b+k*c) up to 622699582951 and 
verify that 3^m = 34 mod m does not hold.

In fact, one quickly shows with this method that n cannot be a multiple 
of 5, 7, 11, 13.
Therefore the test in step 3) can be slightly sharpened to "If 
gcd(b,c,2*3*5*7*11*13*17)>1", hoping to avoid a few lengthy computations 
in step 4).
Since one prime divisor of n must be <srqt(622699582951, I ran the above 
exclusion algorithm overnight against all primes  100 < p <= 789109 plus 
those primes p < 100 that  require less than 10^7 loops in step 4).
After this, the only primes left are:  19, 31, 43, 47, 53, 79.
For these primes, I ran the algorithm against all products of two of 
these primes (including squares).
After that, the only possibilities still left are: n = p*q where p in 
{19, 31, 43, 47, 53, 79} and q is a prime > 789109.
In this case, q must be a divisor of 3^p-34.
Here are the complete factorizations of 3^p-34 (Some big prime factors 
were obtained via http://www.alpertron.com.ar/ECM.HTM):
3^19 - 34 = 53 * 21929461
3^31 - 34 = 31*199*739*135487643
3^43 - 34 = 263*1248125351310026911
3^47 - 34= 1819851367 * 14610431841359
3^53 - 34= 384227 * 1726913711 * 29212450037
3^79 - 34 is prime
Therefore, we are done after explicitly testing the following values of 
n: 19*21929461, 31*135487643, 47*1819851367, 53*384227, 53*1726913711.





More information about the SeqFan mailing list