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