cp's OEIS Frontend

A330292 a(n) = number of integers 1 <= k < n such that omega(k) <= omega(n), where omega = A001221.

%I A330292 #56 Dec 12 2019 11:40:36
%S A330292 0,1,2,3,4,5,5,6,7,9,8,11,9,13,14,10,11,17,12,19,20,21,13,23,14,25,15,
%T A330292 27,16,29,17,18,31,32,33,34,19,36,37,38,20,41,21,41,42,43,22,45,23,47,
%U A330292 48,49,24,51,52,53,54,55,25,59,26,58,59,27,61,65,28,63,64
%N A330292 a(n) = number of integers 1 <= k < n such that omega(k) <= omega(n), where omega = A001221.
%C A330292 Any natural number n can be represented as n = (k_1)^p_1 * (k_2)^p_2 * ... * (k_h)^p_h, where k_i is prime for any i from 1 to h. Let us consider the function omega(n) = h, which represents the number of distinct prime factors of n. Then a(k) is the number of positive integers j less than k for which the value of function omega(j) is <= omega(k).
%C A330292 a(P) = A025528(P) for P a prime power in A246655.
%C A330292 a(Q) = Q - 1 for Q a primorial number in A002110.
%C A330292 Let us consider n > k such that omega(n) = omega(k) = omega and there is no w such that n > w > k and omega(w) > omega. Hence a(n) - a(k) = n - k.
%H A330292 Felix Fröhlich, <a href="/A330292/b330292.txt">Table of n, a(n) for n = 1..10000</a>
%e A330292 a(1) = 0: 1 has no predecessor, omega(1) = 0 by convention;
%e A330292 a(2) = 1 because omega(2) = 1, 1 >= omega(0);
%e A330292 a(3) = 2 because omega(3) = 1 and none of omega(1), omega(2) >= 1;
%e A330292 a(4) = 3 because omega(4) = 1 and none of omega(1), omega(2), omega(3) >= 1.
%t A330292 a[n_] := Block[{t = PrimeNu[n]}, Length@ Select[Range[n - 1], PrimeNu[#] <= t &]]; Array[a, 70] (* _Giovanni Resta_, Dec 10 2019 *)
%o A330292 (Python)
%o A330292 def primes(n):
%o A330292     divisors = [ d for d in range(2,n//2+1) if n % d == 0 ]
%o A330292     return [ d for d in divisors if \
%o A330292              all( d % od != 0 for od in divisors if od != d ) ]
%o A330292 pprimes = {}
%o A330292 for i in range(1, 10000):
%o A330292     res = len(primes(i))
%o A330292     if res == 0:
%o A330292         res = 1
%o A330292     pprimes[i] = res
%o A330292 for k in range(1, 10000):
%o A330292     s = 0
%o A330292     for i in range(1, k):
%o A330292         if pprimes[i] <= pprimes[k]:
%o A330292             s+=1
%o A330292     print(s)
%o A330292 (PARI) for(n=1,70,my(omn=omega(n),m=0);for(k=1,n-1,if(omega(k)<=omn,m++));print1(m,", ")) \\ _Hugo Pfoertner_, Dec 10 2019
%o A330292 (PARI) a(n) = my(omn=omega(n)); sum(k=1, n-1, omega(k) <= omn); \\ _Michel Marcus_, Dec 11 2019
%Y A330292 Cf. A001221 (omega), A025528, A246655, A002110.
%K A330292 nonn,easy
%O A330292 1,3
%A A330292 _Dilshod Urazov_, Dec 10 2019
%E A330292 More terms from _Giovanni Resta_, Dec 10 2019