Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Lehmer's problem
Replies: 35   Last Post: Oct 13, 2001 9:25 AM

 Messages: [ Previous | Next ]
 Phil Carmody Posts: 62 Registered: 12/13/04
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