f(n)=aantal koppels (x,y) waarvoor kgv(x,y)=n

[IAmNotDutch]

Sorry, just wanted to be safe in case it was against moderator rules or something.

Consider N=25 so g(25)

The primes underneath it are
A=[2, 3, 5] and B=[7, 11, 13, 17, 19, 23]
I separated them out because nothing in B will need to be multiplied against each other and will have exponent=1 at most. The cutoff point between A and B is sqrt(N).

The maximum power for a given prime is log(N,prime), giving us:
eA=[4, 2, 2] and eB=[1, 1, 1, 1, 1, 1] although eB is obvious.
But at least we know how much to inflate, at most, for each prime. At most, we will only take one number from B with any combination of primes and exponents from A.

Then it is a matter of intelligently iterating through all possible powers for all possible primes, stopping early so we don't waste time. For example, if I take 3*5 from A then 7 from B, and I know 3*5*7 is too large, then I also know 3*5*11 will be too large so I don't have to bother going through the rest of B.

For each unique prime factorization we attain, we add to our total the amount ((2*a1+1)(2*a2+2)...(2*an+1)+1)/2) for each exponent. This gives us g(n).

Again I don't know if this is the right approach because I haven't solved it yet. But this is merely my current intuition. My computer science abilities are not strong when it comes to generating all combinations of something.

PS: For 10**12, primelist A would have 78498 primes. That is the only really hard part in my opinion... the number of combinations is very large and I am not sure how to intelligently process them. It may not be a big problem because as long as we cut off early we will ignore anything past it.

[op=op]

x en y moeten toch kleiner blijven dan B=2
en bijgevolg kunnen en (exponent van 2) toch nooit 2 worden.

Nee hoor, dat wordt nergens beweerd.

[op=op]

Consider N=25 so g(25)

You use and and I think they are the same.

I think ,
where is the sum of the divisors of k.

The problem with your idea (until now) is that you have to scan through 1000000000000 numbers to filter out the primes. That is too much work.

[wnvl]

From this you can either use a convolution argument or a Perron formula type argument to get an asymptotic formula. In particular, I believe it follows that



With more work, you can get lower-order terms of size ≍xlogx and ≍x.

Eens nadenken of het mogelijk is om dit te verfijnen. Heb nog nooit gehoord van "Perron formula type" en die convolutie is mij ook nog niet duidelijk.

[IAmNotDutch]

Consider N=25 so g(25)

You use and and I think they are the same.

I think ,
where is the sum of the divisors of k.

The problem with your idea (until now) is that you have to scan through 1000000000000 numbers to filter out the primes. That is too much work.

Getting the prime list is easy with the Sieve of Eratosthenes; takes only a couple seconds

[wnvl]

Consider N=25 so g(25)

You use and and I think they are the same.

I think ,
where is the sum of the divisors of k.

The problem with your idea (until now) is that you have to scan through 1000000000000 numbers to filter out the primes. That is too much work.

Getting the prime list is easy with the Sieve of Eratosthenes; takes only a couple seconds

Between 0 and 10^12, there are 37,607,912,018 primes. I invite you to do this in a couple of seconds...

[David]

I am not a moderator, but for me it is no problem that you contribute to this topic in English.

The administrators verdict is final IMO but I don't care if it's english. It is more readable most for members on the other board you posted this problem.

[IAmNotDutch]

Between 0 and 10^12, there are 37,607,912,018 primes. I invite you to do this in a couple of seconds...

You only need to generate up to sqrt(N). You don't need to hold the rest in memory because, again, they're either all exponent 0 or one of them is exponent 1. It becomes an exercise of iterating up the B list for every A combination.

[wnvl]

I am not a moderator, but for me it is no problem that you contribute to this topic in English.

The administrators verdict is final IMO but I don't care if it's english. It is more readable most for members on the other board you posted this problem.

Goed. Al is er op de andere boards nog niet veel reactie

http://www.mymathforum.com/viewtopic.php?f=40&t=29805
http://math.stackexchange.com/questions ... or-squares

[op=op]

When you need the highest prime, you have to sieve through about 10^12 integers.

De volgende zeef zou heel snel zijn en heeft geen array-grenzen beperking. Ik heb versie 2 gedownload.
Het is een keurig programma geschreven in C.
Wie C kent heeft er misschien iets aan.

[IAmNotDutch]

With my current sieve:
For 10**6 it takes 0.004s to generate the necessary primes.
For 10**12 it takes 0.29s to generate the necessary primes.

So generating the primes isn't the challenge. It's intelligently looping through the necessary combinations so you can determine g(n) quickly.

[wnvl]

Between 0 and 10^12, there are 37,607,912,018 primes. I invite you to do this in a couple of seconds...

You only need to generate up to sqrt(N). You don't need to hold the rest in memory because, again, they're either all exponent 0 or one of them is exponent 1. It becomes an exercise of iterating up the B list for every A combination.

I see what you mean, you only need the number of primes between 10^6 and 10^12 which is available on the internet. But the crux is now how to deal with all possible combinations of primes between 0 and .

[IAmNotDutch]

I see what you mean. But the crux is now how to deal with all possible combinations of primes between 0 and .

Correct

Again, I could be wrong, but based on the notion that f(n) is equal to a Diophantine that was brought up in earlier PE questions... I think it is a good bet to make.

[IAmNotDutch]

Another optimization to consider:

Say we have a combination of primes list A (along with their exponents). Call this value VA.

We want to know how many items from list B we can multiply by to stay under limit N.

N/VA= the maximum bound for a B prime we can multiply VA by. We then need a fast way to count primes between sqrt(N) and B. Let this count be X. Then we simply add to our total X*processExponents(current exponents of VA extended by 1 exponent).

When it comes to creating combinations in A, we want to start high and work our way down, because once we have a valid solution, that solution will be valid for all lower exponents and we don't have to test any of them.

[wnvl]

still think the numbers are too large for this kind of algorithm (too many combinations with primes between 0 and ), but up to you to convince me of the opposite...