|
|
A027424
|
|
Number of distinct products ij with 1 <= i, j <= n (number of distinct terms in n X n multiplication table).
|
|
34
|
|
|
1, 3, 6, 9, 14, 18, 25, 30, 36, 42, 53, 59, 72, 80, 89, 97, 114, 123, 142, 152, 164, 176, 199, 209, 225, 239, 254, 267, 296, 308, 339, 354, 372, 390, 410, 423, 460, 480, 501, 517, 558, 575, 618, 638, 659, 683, 730, 747, 778, 800, 827, 850, 903
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
As n->infinity what is an asymptotic expression for a(n)? Reply from Carl Pomerance: Erdős showed that a(n) is o(n^2). Linnik and Vinogradov (1960) showed it is O(n^2/(log n)^c) for some c > 0. Finer estimations were achieved in the book Divisors by Hall and Tenenbaum (Cambridge, 1988), see Theorem 23 on p. 33.
An easy lower bound is to consider primes p > n/2, times anything < n. This gives n^2/(2 log n). - Richard C. Schroeppel, Jul 05 2003
A033677(n) is the smallest k such that n appears in the k X k multiplication table and a(k) is the number of n with A033677(n) <= k.
Erdős showed in 1955 that a(n)=O(n^2/(log n)^c) for some c>0. In 1960, Erdős proved a(n) = n^2/(log n)^(b+o(1)), where b = 1-(1+loglog 2)/log 2 = 0.08607... In 2004, Ford proved a(n) is bounded between two positive constant multiples of n^2/((log n)^b (log log n)^(3/2)). - Kevin Ford (ford(AT)math.uiuc.edu), Apr 20 2006
|
|
REFERENCES
|
Hall, Richard Roxby, and Gérald Tenenbaum. Divisors. Cambridge University Press, 1988.
Y. V. Linnik and I. M. Vinogradov, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960), 41-49 (in Russian).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{L=1..n^2} Sum_{d|L} moebius(L/d) * floor( m(d,n) * n / L ), where m(d,n) is the maximum divisor of d not exceeding n. - Max Alekseyev, Jul 14 2011
n^2 = Sum_{m=1..n^2} Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n]
a(n) = Sum_{m=1..n^2} sign( Sum_{k=1..n^2} [k|m]*[m <= n*k]*[k <= n] ), conjecture.
(End)
|
|
MAPLE
|
A027424m := proc(d, n)
local a, dvs ;
a := 0 ;
for dvs in numtheory[divisors](d) do
if dvs <= n then
a := max(a, dvs) ;
end if;
end do:
a ;
end proc:
add(add(numtheory[mobius](L/d) *floor(A027424m(d, n) *n/L), d=numtheory[divisors](L)), L=1..n^2) ;
end proc:
|
|
MATHEMATICA
|
u = {}; Table[u = Union[u, n*Range[n]]; Length[u], {n, 100}] (* T. D. Noe, Jan 07 2012 *)
|
|
PROG
|
(PARI) multab(N)=local(v, cv, s, t); v=vector(N); cv=vector(N*N); v[1]=cv[1]=1; for(k=2, N, s=0:for(l=1, k, t=k*l: if(cv[t]==0, s++); cv[t]++); v[k]=v[k-1]+s); v \\ Ralf Stephan
(PARI) A027424(n)={my(u=0); sum(j=1, n, sum(i=1, j, !bittest(u, i*j) & u+=1<<(i*j)))} \\ M. F. Hasler, Oct 08 2012
(PARI) a(n) = #setbinop((x, y)->x*y, vector(n, i, i); ); \\ Michel Marcus, Jun 19 2015
(Haskell)
import Data.List (nub)
a027424 n = length $ nub [i*j | i <- [1..n], j <- [1..n]]
(Python)
def A027424(n): return len({i*j for i in range(1, n+1) for j in range(1, i+1)}) # Chai Wah Wu, Oct 13 2023
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|