A008479 Number of numbers <= n with same prime factors as n.

1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 4, 2, 1, 3, 2, 1, 1, 1, 5, 1, 1, 1, 5, 1, 1, 1, 3, 1, 1, 1, 2, 2, 1, 1, 6, 2, 4, 1, 2, 1, 7, 1, 3, 1, 1, 1, 2, 1, 1, 2, 6, 1, 1, 1, 2, 1, 1, 1, 8, 1, 1, 3, 2, 1, 1, 1, 5, 4, 1, 1, 2, 1, 1, 1, 3, 1, 3, 1, 2, 1, 1, 1, 9

Offset

1,4

Comments

For n > 1, a(n) gives the (one-based) index of the row where n is located in arrays A284311 and A285321 or respectively, index of the column where n is in A284457. A285329 gives the other index. - Antti Karttunen, Apr 17 2017

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

P. Erdős, T. Motzkin, Problem 5735, Amer. Math. Monthly, 78 (1971), 680-681. (Incorrect solution!)

H. N. Shapiro, Problem 5735, Amer. Math. Monthly, 97 (1990), 937.

Formula

a(n) = Sum_{k=1..n} (floor(n^k/k)-floor((n^k-1)/k))*(floor(k^n/n)-floor((k^n-1)/n)). - Anthony Browne, May 20 2016

If A008683(n) <> 0 [when n is squarefree, A005117], a(n) = 1, otherwise a(n) = 1+a(A285328(n)). - Antti Karttunen, Apr 17 2017

Maple

N:= 100: # to get a(1)..a(N)
V:= Vector(N):
V[1]:= 1:
for n from 2 to N do
  if V[n] = 0 then
   S:= {n};
   for p in numtheory:-factorset(n) do
     S := S union {seq(seq(s*p^k, k=1..floor(log[p](N/s))), s=S)};
   od:
   S:= sort(convert(S, list));
   for k from 1 to nops(S) do V[S[k]]:= k od:
fi
od:
convert(V, list); # Robert Israel, May 20 2016

Mathematica

PkTbl=Prepend[ Array[ Times @@ First[ Transpose[ FactorInteger[ # ] ] ]&, 100, 2 ], 1 ]; 1+Array[ Count[ Take[ PkTbl, #-1 ], PkTbl[ [ # ] ] ]&, Length[ PkTbl ] ]
Count[#, k_ /; k == Last@ #] & /@ Function[s, Take[s, #] & /@ Range@ Length@ s]@ Array[Map[First, FactorInteger@ #] &, 120] (* or *)
Table[Sum[(Floor[n^k/k] - Floor[(n^k - 1)/k]) (Floor[k^n/n] - Floor[(k^n - 1)/n]), {k, n}], {n, 120}] (* Michael De Vlieger, May 20 2016 *)

Prog

(Scheme) (define (A008479 n) (if (not (zero? (A008683 n))) 1 (+ 1 (A008479 (A285328 n))))) ;; Antti Karttunen, Apr 17 2017
(PARI) a(n)=my(f=factor(n)[, 1], s); forvec(v=vector(#f, i, [1, logint(n, f[i])]), if(prod(i=1, #f, f[i]^v[i])<=n, s++)); s \\ Charles R Greathouse IV, Oct 19 2017

Crossrefs

Cf. A005117 (positions of ones), A005361, A007947, A008683, A284311, A284457, A285321, A285328, A285329.

Sequence in context: A303915 A322885 A292582 * A331178 A227350 A107345

Adjacent sequences: A008476 A008477 A008478 * A008480 A008481 A008482

Keyword

nonn,easy

Author

Jeffrey Shallit, Olivier Gérard

Status

approved