Project Euler Forum

Hello,
I had a question about this. If I got it right, to find

f(n)
I would have to find the number of pairs (x,y), such that x&Y are positive integers, x<=y and LCM(x,y) == n.
But doesn't this give an infinite number of ways ?

For example, if I am trying to find f(2), can't x&y be any pair of even numbers ( with x<=y ) ?
(2,2) (2,4) (4,8) ...... ( 2x, 4x ) .... etc.

Or maybe I misunderstood some part of the question ?

LCM(2,4)=4 and LCM(4,8)=8.

Don't confuse LCM with GCF.

If LCM(x,y) = n, y must be a factor of n, making n a multiple of y.

Yes that's true.
But also GCD(4,8)=4 and not 2 and GCD(2x,4x)=2x.
As LCM(a,b)=a*b/(GCD(a,b), it follows that LCM(2x,4x)=2x*4x/2x=4x.

sorry... it is deleted.

@ stevcis:
this forum isn't a place to discuss solution methods.
Could you be so kind to remove your post?

"Somewhere things get wrong"

For g(10₄ I get 363,982 that's right.
For g(10⁶) I get 73,858,790 which is equal to (2*37,429,395)-10⁶.

I am unable to see where is my mistake.

Please don't start a new topic if there already exists one for that problem.

@william 2a

how do you know g(10^4) is 363982 if g(10^6) is wrong and the only hint we're given from PE is for 10^6???

@hk: Sorry.

I found the first ten values (1, 3, 3, 5, 3, 9, 3, 7, 5, 9) by brute forcing.

These values gave me the A048691 sequence in OEIS where I found a link to the first 10⁴ values.

A little program in PARI gave me the sum of these values.

@ WILLIAM 2a

i'd look carefully at those first 10 values... if your sequence means that 1 is the LCM for 1 pair, 2 is the LCM for 3 pairs, 3 is the LCM for 3 pairs, 4 is the LCM for 5 pairs, then i think careful examination of just the number 2 would suggest there is something wrong with the brute force algorithm.
i get 1,2,2,3,2,5,2,4,3,5 which is the same as yours except your 3s are 2s, your 5s are 3s, your 9s are 5s and your 7s are 4s.

f(10,000) should be 186993 according to my algorithm which correctly gets g(10^6).

btw i have no idea how to solve the actual question but i do get g(10^6). 10^12 is just a darn big number

william2a wrote:"Somewhere things get wrong"

For g(10₄ I get 363,982 that's right.
For g(10⁶) I get 73,858,790 which is equal to (2*37,429,395)-10⁶.

I am unable to see where is my mistake.

Did you notice the constraint "x ≤ y"? I think your numbers are "right" if you ignore that.

@stevcis

Many thanks for your help.
I continue my search.

stevcis wrote: f(10,000) should be 186993 according to my algorithm which correctly gets g(10^6).

Ack! I get 186991! No idea how I'm going to debug that!

*sighs*
Perlkönig