Wiskundeforum

What about using the Sieve in reverse and counting exponents along the way to N?

I don't mean to discourage current efforts but I am fairly certain that the answer will be more easily achievable through iterations/sieving rather than a mathematical approximation. I am beginning to think that this will come down to an exercise in modifying the Sieve effectively.

Is 10**12 high enough to make that converge?

g(A) = \sum_{k=1}^A n(k)2^{\tau(k)-1} , where n(k) = r if \frac{A}{r+1} < k \le \frac{A}{r} . \tau(k) is the number of prime factors of k . E.g. \tau(2^73^511)=3 The \tau values may be calculated by a sieve: array \tau[2..n]= (0..0) Add 1 to \tau(m) if m is even. The first m>2 with \tau(m)=0 is 3. ...

Sorry; yes I mean up until sqrt(n).

Calculating the primes for all 10**12 is too long, but it isn't necessary anyway

I agree it is tough, but that's what 110 was all about, and solutions ran in milliseconds. Of course there are many primes to deal with now, but I can't think of a better approach currently. I could be totally wrong! Just offering ideas.

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 ...

wnvl schreef: 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.

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.

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 ...

Consider N=25 so g(25) You use f(n) and g(n) and I think they are the same. I think g(n) = \{(x,y) | x\le y \wedge \mbox{ lcm}(x,y)\le n\} = \frac12 (\sum_{k=1}^n d(k^2) + n) , where d(k) is the sum of the divisors of k. The problem with your idea (until now) is that you have to scan through 100000...

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. T...

f (n) = ((tau ^ 2) -1) / 2 maar ook gelijk aan ((2A1 +1) (2A2 +1) (2A3 +1) ... (2an +1) +1) / 2 waarbij ai is een exponent van het grootste pi. Bijvoorbeeld f (10) is 5 door 10 = 2 ^ 1 * 5 ^ 1 en ((2 * 1 +1) * (2 * 1 +1) +1) / 2 = (9 +1) / 2 = 5 g (n) is deze exponent som van alle f (n). Als we denk...

Ja. 110 wordt grotendeels opgelost door degenen die geleerd echt goed algoritme gepost in het forum 108 (108 niet nodig iets te luxe). Op zijn beurt Ik denk dat 379 gaat grotendeels kunnen worden opgelost door degenen die opgelost 110. Het idee achter 110 is het manipuleren van bevoegdheden van een ...

Het meeste van wat jullie zeggen is wat ik hebben gekeken naar al, maar ik wilde dit toe te voegen:

f (n) = (tau(n^2)+1)/2 = aantal geldige oplossingen 1 / n = 1 / x + 1 / y. Het is een Diophantische vergelijking, opgenomen in problemen 108 en 110.