cp's OEIS Frontend

A078898 Number of times the smallest prime factor of n is the smallest prime factor for numbers <= n; a(0)=0, a(1)=1.

%I A078898 #65 Mar 03 2025 20:24:46
%S A078898 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,
%T A078898 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,
%U A078898 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
%N A078898 Number of times the smallest prime factor of n is the smallest prime factor for numbers <= n; a(0)=0, a(1)=1.
%C A078898 From _Antti Karttunen_, Dec 06 2014: (Start)
%C A078898 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.
%C A078898 (End)
%H A078898 Harvey P. Dale (terms 1 - 1000) & Antti Karttunen, <a href="/A078898/b078898.txt">Table of n, a(n) for n = 0..10000</a>
%F A078898 Ordinal transform of A020639 (Lpf). - _Franklin T. Adams-Watters_, Aug 28 2006
%F A078898 From _Antti Karttunen_, Dec 05-08 2014: (Start)
%F A078898 a(0) = 0, a(1) = 1, a(n) = 1 + a(A249744(n)).
%F A078898 a(0) = 0, a(1) = 1, a(n) = sum_{d | A002110(A055396(n)-1)} moebius(d) * floor(n / (A020639(n)*d)).
%F A078898 a(0) = 0, a(1) = 1, a(n) = sum_{d | A002110(A055396(n)-1)} moebius(d) * floor(A032742(n) / d).
%F A078898 [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].
%F A078898 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).]
%F A078898 For n > 1: a(n) = A249810(n) - A249820(n).
%F A078898 (End)
%F A078898 Other identities:
%F A078898 a(2*n) = n.
%F A078898 For n > 1: a(n)=1 if and only if n is prime.
%F A078898 For n > 1: a(n) = A249808(n, A055396(n)) = A249809(n, A055396(n)).
%F A078898 For n > 1: a(n) = A246277(A249818(n)).
%F A078898 From _Antti Karttunen_, Jan 04 2015: (Start)
%F A078898 a(n) = 2 if and only if n is a square of a prime.
%F A078898 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.
%F A078898 (End)
%F A078898 a(A000040(n)^2) = 2; a(A000040(n)*A000040(n+1)) = 3. - _Reinhard Zumkeller_, Apr 06 2015
%F A078898 Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Sum_{k>=1} (A038110(k)/A038111(k))^2 = 0.2847976823663... . - _Amiram Eldar_, Oct 26 2024
%p A078898 N:= 1000: # to get a(0) to a(N)
%p A078898 Primes:= select(isprime, [2,seq(2*i+1,i=1..floor((N-1)/2))]):
%p A078898 A:= Vector(N):
%p A078898 for p in Primes do
%p A078898   t:= 1:
%p A078898   A[p]:= 1:
%p A078898   for n from p^2 to N by p do
%p A078898     if A[n] = 0 then
%p A078898        t:= t+1:
%p A078898        A[n]:= t
%p A078898     fi
%p A078898   od
%p A078898 od:
%p A078898 0,1,seq(A[i],i=2..N); # _Robert Israel_, Jan 04 2015
%t A078898 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 *)
%o A078898 (PARI)
%o A078898 \\ Not practical for computing, but demonstrates the sum moebius formula:
%o A078898 A020639(n) = { if(1==n,n,vecmin(factor(n)[, 1])); };
%o A078898 A055396(n) = { if(1==n,0,primepi(A020639(n))); };
%o A078898 A002110(n) = prod(i=1, n, prime(i));
%o A078898 A078898(n) = { my(k,p); if(1==n, n, k = A002110(A055396(n)-1); p = A020639(n); sumdiv(k, d, moebius(d)*(n\(p*d)))); };
%o A078898 \\ _Antti Karttunen_, Dec 05 2014
%o A078898 (Scheme)
%o A078898 ;; With memoizing definec-macro.
%o A078898 (definec (A078898 n) (if (< n 2) n (+ 1 (A078898 (A249744 n)))))
%o A078898 ;; Much better for computing. Needs also code from A249738 and A249744. - _Antti Karttunen_, Dec 06 2014
%o A078898 (Haskell)
%o A078898 import Data.IntMap (empty, findWithDefault, insert)
%o A078898 a078898 n = a078898_list !! n
%o A078898 a078898_list = 0 : 1 : f empty 2 where
%o A078898    f m x = y : f (insert p y m) (x + 1) where
%o A078898            y = findWithDefault 0 p m + 1
%o A078898            p = a020639 x
%o A078898 -- _Reinhard Zumkeller_, Apr 06 2015
%Y A078898 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.
%Y A078898 Cf. A001248, A006094, A038110, A038111, A090076.
%K A078898 nonn
%O A078898 0,5
%A A078898 _Reinhard Zumkeller_, Dec 12 2002
%E A078898 a(0) = 0 prepended for recurrence's sake by _Antti Karttunen_, Dec 06 2014