[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