cp's OEIS Frontend

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

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