Counting Integers and their Multiplicities
 

Let [I]S[/I][sub][I]n[/I][/sub] = {1 ≤ [I]i[/I] ≤ [I]n[/I]} be the set of positive integers not exceeding [I]n[/I].
Let
[tex]M_{m,n}=\bigcup_{1\leq i \leq m}i S_n[/tex]
be the union of all integers in S[sub][I]n[/I][/sub] times 1, 2, ..., [I]m[/I].

Is there a simple expression for |[I]M[/I][sub][I]m[/I],[I]n[/I][/sub]|?
Or a simple expression for [I]r[/I]([I]m[/I]) = lim[sub][I]n[/I]→∞[/sub] |[I]M[/I][sub][I]m[/I],[I]n[/I][/sub]|/n ? For [I]m[/I]=1, 2, 3, 4, 5, 6, 7 they are [I]r[/I]([I]m[/I]) = 1, 3/2, 2, 29/12, 44/15, 33/10, 134/35 respectively. What about larger [I]m[/I]? Does the ratio [I]r[/I]([I]m[/I])/[I]m[/I] converge as [I]m[/I] increases?

Alex

Did you try inputting the first few terms into

[url]http://www.research.att.com/~njas/sequences/[/url]

If there's an easy formula, this site probably has it.

good luck!

[quote=masser;101063]Did you try inputting the first few terms into

[URL]http://www.research.att.com/~njas/sequences/[/URL]
[/quote]... after transforming all terms into integers, that is ...

I multiplied by 420 and entered:

420,630,840,1015,1232,1386,1608

Got

"I am sorry, but the terms do not match anything in the table."

Does r(m)/m converge? You can show that r(m)/m is bounded by 0 and 1; it also looks like r(m)/m is decreasing - if you can prove this; the sequence converges. Is this really a homework question? It's a nifty question. :geek:

No, it's not a homework question. I stumbled upon it during some coding work gor GMP-ECM. At some point, we'll have to scale some residues by a^1, a^2, ..., a^n, a^2, a^4, a^6, ..., etc, until a^m, a^(2m), ..., a^(mn). I had wondered how much computation I could save by avoiding recomputing of powers that were encountered before. When I asked the guys here at Loria, we got the first couple of terms very quickly, but a closed form formula for anything proved much harder to get than I had anticipated - I thought this sort of problem probably was classical with a famous solution.

If anyone has any ideas, or pointers to the literature, please let me know!

Also, this isn't a homework exercise (except maybe for the most diabolical of teachers!) so I'll move it back to Math.

Alex

masser: r(m)/m is clearly bounded by 0 and 1, however, it is not monotonically decreasing. Emmanuel Thomé wrote Magma code that estimates the ratio reasonably quickly for 1 ≤ m ≤ 200. Graph is attached.

Alex

Should have guessed it would not be that easy...

Is that limiting value e^(-1)?

Looks like 1/log(log n) to me. Can you make the data of Thomé available, Alex? Have you tried any curve-fitting to it?

[QUOTE=philmoore;101188]Looks like 1/log(log n) to me. Can you make the data of Thomé available, Alex? Have you tried any curve-fitting to it?[/QUOTE]

It is attached.

I haven't worked very hard on this problem yet as it is not strictly necessary for writing GMP-ECM, which is what keeps me busy atm. However, I think it's an interesting problem as it looks so innocent and cute at first glance, but when you try to get a grip on it, it blows up right in your face!

Alex

Here's a q-n-d manual fit with 1/(c*loglog(n)). It's close, but not quite right.

Alex

We have [tex]M_{m,n}=M_{m,n}[/tex] , right ?

You consider in particular [tex]\lim_{m\to\infty} (\lim_{n\to\infty}|M_{m,n}|/n)/m[/tex]

Which might be [tex]\lim_{n\to\infty}|M_{n,n}|/n^2[/tex]

Which is the probability that a random integer has no prime factor greater than its square root.