A008479 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

Paul Erdős and 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

a(n) <= A010846(n), with equality if and only if n = 1. - Amiram Eldar, May 25 2025

a(m^(k+1)) = A010846(m^k) when m is squarefree. - Flávio V. Fernandes, Aug 20 2025

a(n) = Product_{j all distinct} A010846(A182944(j,k)) where n=A182944(j,k+1). - Flávio V. Fernandes, Nov 11 2025

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:

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

(Python)

from functools import lru_cache

from sympy import primefactors, integer_log

def A008479(n):

if n == 1: return 1

ps = tuple(sorted(primefactors(n)))

@lru_cache(maxsize=None)

def g(x, m): return 0 if x == 1 else sum(g(x//ps[m]**i, m-1) for i in range(1, integer_log(x, ps[m])[0]+1)) if m else integer_log(x, ps[0])[0]

return g(n, len(ps)-1) # Chai Wah Wu, Apr 04 2026

CROSSREFS

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

Cf. A010846; A182944; A005117, A019565.