|
%I #30 Oct 19 2017 10:53:38
%S 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,
%T 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,
%U 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
%N Number of numbers <= n with same prime factors as n.
%C 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
%H T. D. Noe, <a href="/A008479/b008479.txt">Table of n, a(n) for n = 1..10000</a>
%H P. Erdős, T. Motzkin, <a href="http://www.jstor.org/stable/2316593">Problem 5735</a>, Amer. Math. Monthly, 78 (1971), 680-681. (Incorrect solution!)
%H H. N. Shapiro, <a href="http://www.jstor.org/stable/2324350">Problem 5735</a>, Amer. Math. Monthly, 97 (1990), 937.
%F 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
%F If A008683(n) <> 0 [when n is squarefree, A005117], a(n) = 1, otherwise a(n) = 1+a(A285328(n)). - _Antti Karttunen_, Apr 17 2017
%p N:= 100: # to get a(1)..a(N)
%p V:= Vector(N):
%p V[1]:= 1:
%p for n from 2 to N do
%p if V[n] = 0 then
%p S:= {n};
%p for p in numtheory:-factorset(n) do
%p S := S union {seq(seq(s*p^k,k=1..floor(log[p](N/s))),s=S)};
%p od:
%p S:= sort(convert(S,list));
%p for k from 1 to nops(S) do V[S[k]]:= k od:
%p fi
%p od:
%p convert(V,list); # _Robert Israel_, May 20 2016
%t PkTbl=Prepend[ Array[ Times @@ First[ Transpose[ FactorInteger[ # ] ] ]&, 100, 2 ], 1 ];1+Array[ Count[ Take[ PkTbl, #-1 ], PkTbl[ [ # ] ] ]&, Length[ PkTbl ] ]
%t Count[#, k_ /; k == Last@ #] & /@ Function[s, Take[s, #] & /@ Range@ Length@ s]@ Array[Map[First, FactorInteger@ #] &, 120] (* or *)
%t 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 *)
%o (Scheme) (define (A008479 n) (if (not (zero? (A008683 n))) 1 (+ 1 (A008479 (A285328 n))))) ;; _Antti Karttunen_, Apr 17 2017
%o (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
%Y Cf. A005117 (positions of ones), A005361, A007947, A008683, A284311, A284457, A285321, A285328, A285329.
%K nonn,easy
%O 1,4
%A _Jeffrey Shallit_, _Olivier Gérard_
|
