|
|
A078898
|
|
Number of times the smallest prime factor of n is the smallest prime factor for numbers <= n; a(0)=0, a(1)=1.
|
|
94
|
|
|
0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 6, 1, 7, 3, 8, 1, 9, 1, 10, 4, 11, 1, 12, 2, 13, 5, 14, 1, 15, 1, 16, 6, 17, 3, 18, 1, 19, 7, 20, 1, 21, 1, 22, 8, 23, 1, 24, 2, 25, 9, 26, 1, 27, 4, 28, 10, 29, 1, 30, 1, 31, 11, 32, 5, 33, 1, 34, 12, 35, 1, 36, 1, 37, 13, 38, 3, 39, 1, 40, 14, 41, 1, 42, 6, 43
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
For n >= 2, a(n) tells in which column of the sieve of Eratosthenes (see A083140, A083221) n occurs in. A055396 gives the corresponding row index.
(End)
|
|
LINKS
|
|
|
FORMULA
|
a(0) = 0, a(1) = 1, a(n) = 1 + a(A249744(n)).
[Instead of Moebius mu (A008683) one could use Liouville's lambda (A008836) in the above formulas, because all primorials (A002110) are squarefree. A020639(n) gives the smallest prime dividing n, and A055396 gives its index].
a(0) = 0, a(1) = 1, a(2n) = n, a(2n+1) = a(A250470(2n+1)). [After a similar recursive formula for A246277. However, this cannot be used for computing the sequence, unless a definition for A250470(n) is found which doesn't require computing the value of A078898(n).]
(End)
Other identities:
a(2*n) = n.
For n > 1: a(n)=1 if and only if n is prime.
a(n) = 2 if and only if n is a square of a prime.
For all n >= 1: a(A251728(n)) = A243055(A251728(n)) + 2. That is, if n is a semiprime of the form prime(i)*prime(j), prime(i) <= prime(j) < prime(i)^2, then a(n) = (j-i)+2.
(End)
|
|
MAPLE
|
N:= 1000: # to get a(0) to a(N)
Primes:= select(isprime, [2, seq(2*i+1, i=1..floor((N-1)/2))]):
A:= Vector(N):
for p in Primes do
t:= 1:
A[p]:= 1:
for n from p^2 to N by p do
if A[n] = 0 then
t:= t+1:
A[n]:= t
fi
od
od:
|
|
MATHEMATICA
|
Module[{nn=90, spfs}, spfs=Table[FactorInteger[n][[1, 1]], {n, nn}]; Table[ Count[ Take[spfs, i], spfs[[i]]], {i, nn}]] (* Harvey P. Dale, Sep 01 2014 *)
|
|
PROG
|
(PARI)
\\ Not practical for computing, but demonstrates the sum moebius formula:
A020639(n) = { if(1==n, n, vecmin(factor(n)[, 1])); };
A002110(n) = prod(i=1, n, prime(i));
(Scheme, with memoizing definec-macro)
(Haskell)
import Data.IntMap (empty, findWithDefault, insert)
a078898 n = a078898_list !! n
a078898_list = 0 : 1 : f empty 2 where
f m x = y : f (insert p y m) (x + 1) where
y = findWithDefault 0 p m + 1
p = a020639 x
|
|
CROSSREFS
|
Cf. A002110, A008683, A008836, A020639, A032742, A054272, A055396, A078899, A078896, A083140, A083221, A243055, A246277, A249738, A249744, A249808, A249809, A249810, A249820, A249818, A250470, A250474, A250477, A250478, A251719, A251724, A251728.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|