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

IAmNotDutch · Bericht door **IAmNotDutch** » 19 apr 2012, 19:30

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.

Bericht door **op=op** » 19 apr 2012, 20:31

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

If this is true, the problem is solved if you can modify that program to generate $\tau(k)$ 's.

$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.
Now add 1 to $\tau(m)$ for all m = 3k.
The first $m>3$ with $\tau(m)=0$ is 5.
Now add 1 to $\tau(m)$ for all m = 5k.
etc.

Bericht door **wnvl** » 19 apr 2012, 20:41

Note that he/she means generating the primes till $\sqrt{n}$

for 10^6 he/she generates primes till 10^3
for 10^12 he/she generates primes till 10^6

IAmNotDutch · Bericht door **IAmNotDutch** » 19 apr 2012, 20:46

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

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

IAmNotDutch · Bericht door **IAmNotDutch** » 19 apr 2012, 20:49

op=op schreef: $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.
Now add 1 to $\tau(m)$ for all m = 3k.
The first $m>3$ with $\tau(m)=0$ is 5.
Now add 1 to $\tau(m)$ for all m = 5k.
etc.

This is very interesting; what is n(k) exactly? Do you have an example?

Bericht door **op=op** » 19 apr 2012, 20:58

Check it for $g(10^6)$ .

Bericht door **wnvl** » 19 apr 2012, 20:58

Bericht door **wnvl** » 19 apr 2012, 21:16

wnvl schreef:
$\frac{\zeta^3(s)}{\zeta(2s)}=\sum_{n=1}^{\infty}\frac{d(n^2)}{n^s}$

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

$\sum_{n\leq x} d(n^2) = \frac{3}{\pi^2}x \log^2 x +O(x \log x)$

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.

Na wat lezen over de Perron formule en Dirichletconvoluties brengt mij dat tot deze contourintegraal in het complexe vlak.

$g(n) =\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} \frac{\zeta^3(z)}{\zeta(2z)}\frac{n^{z}}{z} dz.\;$

c moet groot genoeg zijn zodat de integraal convergeert.

Op zich is het natuurlijk maar het verleggen van het probleem, want hoe bereken je deze contourintegraal?.
Nieuwsgierig of Wolfram daar iets mee kan.

Bericht door **op=op** » 19 apr 2012, 21:24

$g(n) =\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty} \frac{\zeta^3(z)}{\zeta(2z)}\frac{n^{z}}{z} dz.\;$

Dit is
$g(n) =\frac{1}{2\pi}\int_{-\infty}^{\infty} \frac{\zeta^3(c+it)}{\zeta(2c+2it)}\frac{n^{c+it}}{c+it} dt.\;$

IAmNotDutch · Bericht door **IAmNotDutch** » 19 apr 2012, 21:29

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

Bericht door **op=op** » 19 apr 2012, 21:31

The solution must be a bit larger than 132314136789161. (15 digits).

The argument is a highly oscillating function between -10^35 and +10^35.
Terrible.

Bericht door **wnvl** » 19 apr 2012, 21:34

IAmNotDutch schreef:Is 10**12 high enough to make that converge?

Don't know how to determine the region of convergence...

Bericht door **wnvl** » 19 apr 2012, 22:04

Above the output from mathematica for

n=5
c=10000

Integrate[(Zeta[10000 + I t]^3*5^(10000 + I*t))/(Zeta[20000 + 2* I* t]*(10000 + It)), {t, 0, Infinity}]

IAmNotDutch · Bericht door **IAmNotDutch** » 19 apr 2012, 22:09

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.

Bericht door **op=op** » 19 apr 2012, 22:16

wnvl schreef:

Above the output from mathematica for

n=5
c=10000

Integrate[(Zeta[10000 + I t]^3*5^(10000 + I*t))/(Zeta[20000 + 2* I* t]*(10000 + It)), {t, 0, Infinity}]

c>1 is voldoende. Probeer het integratieinterval in stukjes te knippen.

Wiskundeforum

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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