|
|
Re: Lehmer's problem
Posted:
Oct 8, 2001 10:53 AM
|
|
Jan Kristian Haugland wrote:
>
> I wrote:
>
> > n2 = 55,462,177 = 17 x 23 x 83 x 1709
> >
> > gives (n2-1)/phi(n2) = 9/8.
>
> Just found that 484,662,529 = 13 x 29 x 433 x 2969
> also gives 9/8. :-)
Jan,
Are you finding these by 'brute force'?
Stepping through each number in turn, factorising it, and working out
the Phi and ratio?
Is there some 'sieve-like' method of making it faster?
Thinks...
If you have 80M spare, and are in the realm of 32-bit integers:
(needs 160M if you're in the realm of 64-bit integers)
for a range of 10000000 integers from N to N+10000000
initialise phi[10000000] array to 1
initialise val[10000000] array s.t. val[i]=i
for each prime < sqrt(10000000)
for each power of the prime < 10000000
for each multiple of that power in the block
divide val[i] by prime
multiply phi[i] by some ratio
for each element in the block
if val[i] is not 1
multiply phi[i] by EulerPhi(val[i])
output i, phi[i]
I can't see a 10000000 block taking more than a minute, to be honest,
after a bit of optimisation.
Most of the time is spent on prime=2, (and prime=3 next) so that's the
only thing that needs optimising initially.
Phil
|
|
