A071521 -id:A071521 - cp's OEIS frontend

A100752 a(n) is the number of positive integers <= 10^n that are divisible by no prime exceeding 3.

1, 7, 20, 40, 67, 101, 142, 190, 244, 306, 376, 452, 534, 624, 720, 824, 935, 1052, 1178, 1309, 1447, 1593, 1745, 1905, 2071, 2244, 2424, 2611, 2806, 3006, 3214, 3429, 3652, 3881, 4117, 4360, 4610, 4866, 5131, 5401, 5679, 5964, 6255, 6553, 6859, 7172, 7491

Offset: 0

Robert G. Wilson v, May 27 2005

nonn

A good approximation seems to be ceiling(log(10^n)*log(6*10^n)/(log(3)*log(4))). - Horst H. Manninger, Oct 29 2022

			a(1) = 7 as there are 7 3-smooth numbers less than 10^1 = 10; they are 1, 2, 3, 4, 6, 8, 9. - _David A. Corneth_, Nov 14 2019

David A. Corneth, Table of n, a(n) for n = 0..1999

Cf. A003586, A011557, A071521.
Cf. A066343, A106598, A106600, A107352, A106629.
Row 2 of A253635.

f[n_] := Sum[ Floor@ Log[2, n/3^i] + 1, {i, 0, Log[3, n]}]; Table[ f[10^n], {n, 0, 46}] (* Robert G. Wilson v, Nov 07 2012 *)

from sympy import integer_log
def A100752(n): return sum((10**n//3**i).bit_length() for i in range(integer_log(10**n,3)[0]+1)) # Chai Wah Wu, Oct 23 2024

a(n) = A071521(10^n). - Chai Wah Wu, Oct 23 2024

A080786 Triangle T(n,k) = number of k-smooth numbers <= n, read by rows.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 3, 4, 4, 1, 3, 4, 4, 5, 1, 3, 5, 5, 6, 6, 1, 3, 5, 5, 6, 6, 7, 1, 4, 6, 6, 7, 7, 8, 8, 1, 4, 7, 7, 8, 8, 9, 9, 9, 1, 4, 7, 7, 9, 9, 10, 10, 10, 10, 1, 4, 7, 7, 9, 9, 10, 10, 10, 10, 11, 1, 4, 8, 8, 10, 10, 11, 11, 11, 11, 12, 12, 1, 4, 8, 8, 10, 10, 11, 11, 11, 11, 12, 12, 13, 1, 4

Offset: 1

Reinhard Zumkeller, Mar 12 2003

T(n,n-1) = A014684(n) for n>1;
T(n,2) = A029837(n) for n>1; T(n,3) = A071521(n) for n>2; T(n,5) = A071520(n) for n>4.
A036234(n) = number of distinct terms in n-th row. - Reinhard Zumkeller, Sep 17 2013

			Triangle begins:
.................. 1
................ 1...2
.............. 1...2...3
............ 1...3...4...4
.......... 1...3...4...4...5
........ 1...3...5...5...6...6
...... 1...3...5...5...6...6...7
.... 1...4...6...6...7...7...8...8
.. 1...4...7...7...8...8...9...9...9.

Reinhard Zumkeller, Rows n=1..120 of triangle, flattened
Eric Weisstein's World of Mathematics, Smooth Number.

Cf. A000079, A002473, A003586, A006530, A014684, A029837, A036234, A051037, A051038, A071520, A071521, A080197, A080681, A080682, A080683.

a080786 n k = a080786_tabl !! (n-1) !! (k-1)
a080786_row n = a080786_tabl !! (n-1)
a080786_tabl = map reverse $ iterate f [1] where
   f xs@(x:_) = (x + 1) :
                (zipWith (+) xs (map (fromEnum . (lpf <=)) [x, x-1 ..]))
        where lpf = fromInteger $ a006530 $ fromIntegral (x + 1)
-- Reinhard Zumkeller, Sep 17 2013

A080786 := proc(x,y)
    local a,n ;
    a := 0 ;
    for n from 1 to x do
        if A006530(n) <= y then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Aug 31 2013

P[n_] := FactorInteger[n][[-1, 1]]; P[1]=1; T[n_, k_] := (For[j=0; m=1, m <= n, m++, If[P[m] <= k, j++]]; j); Table[T[n, k], {n, 1, 15}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 22 2015 *)

from itertools import count, islice
from sympy import prevprime, integer_log
def A080786_T(n,k):
    if k==1: return 1
    def g(x,m): return x.bit_length() if m==2 else sum(g(x//(m**i),prevprime(m))for i in range(integer_log(x,m)[0]+1))
    return g(n,prevprime(k+1))
def A080786_gen(): # generator of terms
    return (A080786_T(n,k) for n in count(1) for k in range(1,n+1))
A080786_list = list(islice(A080786_gen(),100)) # Chai Wah Wu, Oct 22 2024

A081063 Number of numbers <= n that are 3-smooth or prime powers.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 12, 12, 12, 13, 14, 15, 16, 16, 16, 16, 17, 18, 19, 19, 20, 20, 21, 21, 22, 23, 23, 23, 23, 24, 25, 25, 25, 25, 26, 26, 27, 27, 27, 27, 28, 29, 30, 30, 30, 30, 31, 32, 32, 32, 32, 32, 33, 33, 34, 34, 34, 35, 35, 35, 36, 36, 36, 36, 37, 38, 39

Offset: 1

Reinhard Zumkeller, Mar 04 2003

nonn

a(n) = #{A081061(k): 1<=k<=n}.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A003586, A000961.

Accumulate[Table[If[PrimePowerQ[n]||Max[FactorInteger[n][[All,1]]]<5,1,0],{n,80}]] (* Harvey P. Dale, Nov 29 2020 *)

from sympy import integer_log, primepi, integer_nthroot
def A081063(n): return int(1-(a:=n.bit_length())-(b:=integer_log(n,3)[0])+sum((n//3**i).bit_length() for i in range(b+1))+sum(primepi(integer_nthroot(n, k)[0]) for k in range(1, a))) # Chai Wah Wu, Sep 16 2024

a(n)=A071521(n)+A065515(n)-A000523(n)-A062153(n)+1.

A096300 Number of positive integers <= n with no prime factor > log(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18

Offset: 1

Ralf Stephan, Aug 03 2004

A. Granville, On positive integers <= x with prime factors <= t log x, Number Theory and Applications (ed. R.A Mollin), (Kluwer, NATO ASI, 1989), 403-422.

a[n_] := Select[Range[n], FactorInteger[#][[-1, 1]] <= Log[n]&] // Length;
a[1] = a[2] = 1;
a /@ Range[75] (* Jean-François Alcover, May 17 2020 *)

a(n)=local(s, t); s=0; for(k=1, n, f=factor(k); t=0; for(l=1, matsize(f)[1], if(f[l, 1]>log(n), t=1; break)); s=s+!t); s

From Charlie Neder, Feb 08 2019: (Start)
a(n) = A000012(n) for 0 < n <= floor(e^2) = 7,
       A070939(n) for 7 < n <= floor(e^3) = 20,
       A071521(n) for 20 < n <= floor(e^5) = 148,
       A071520(n) for 148 < n <= floor(e^7) = 1096,
       A071604(n) for 1096 < n <= floor(e^11) = 59874,
and so on. (End)

A122256 Number of numbers <= n with 3-smooth Euler's totient (A000010).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 20, 20, 21, 21, 22, 23, 24, 24, 25, 25, 26, 26, 27, 28, 29, 30, 31, 32, 33, 33, 34, 34, 34, 35, 35, 35, 36, 36, 36, 37, 38, 38, 39, 39, 40, 41, 41, 41, 42, 42, 42, 43, 44, 45, 45, 45, 46, 46, 47, 47, 48

Offset: 1

Reinhard Zumkeller, Aug 29 2006

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000

Partial sums of A122255.

Cf. A000010, A003586, A071521.

b[n_] := Boole[FactorInteger[EulerPhi[n]][[-1, 1]] <= 3];
Table[b[n], {n, 1, 100}] // Accumulate (* Jean-François Alcover, Oct 14 2021 *)

issm(n) = {my(e = eulerphi(n >> valuation(n, 2))); e >>= valuation(e, 2); e == 3^valuation(e, 3);}
list(lim) = {my(s = 0); for(n = 1, lim, s += issm(n); print1(s, ", "));} \\ Amiram Eldar, May 14 2025

A122258 Number of Pierpont primes <= n.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10

Offset: 1

Reinhard Zumkeller, Aug 29 2006

nonn

Eric Weisstein's World of Mathematics, Pierpont Prime.

Partial sums of A122257.

Cf. A000720, A005109, A071521.

smooth3Q[n_] := Times @@ ({2, 3}^IntegerExponent[n, {2, 3}]) == n; s[n_] := Boole[PrimeQ[n] && smooth3Q[n-1]]; Accumulate[Table[s[n], {n, 1, 100}]] (* Amiram Eldar, May 14 2025 *)

is3smooth(n) = my(m = n >> valuation(n, 2)); m == 3^valuation(m, 3);
f(n) = isprime(n) && is3smooth(n-1);
list(lim) = {my(s = 0); for(n = 1, lim, s += f(n); print1(s, ", "));} \\ Amiram Eldar, May 14 2025

a(n) <= A000720(n).

a(n) <= A071521(n).

A301461 Number of integers less than or equal to n whose largest prime factor is 3.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11

Offset: 0

Ralph-Joseph Tatt, Mar 21 2018

nonn

a(n) increases when n has the form 2^a*3^b, with a >= 0 and b > 0.

A distinct sequence can be generated for each prime number; this sequence is for the prime number 3. For an example using another prime number see A301506.

			a(12) = a(2^2 * 3^1); 3 is the largest prime factor, so a(12) exceeds the previous term by 1. For a(13), 13 is a prime, so there is no increase from the previous term.

Cf. A003586, A065119, A071521.

Cf. A301506, A071521, A070939.

clear;clc;
prime = 3;
limit = 10000;
largest_divisor = ones(1,limit+1);
for k = 0:limit
    f = factor(k);
    largest_divisor(k+1) = f(end);
end
for i = 1:limit+1
    FQN(i) = sum(largest_divisor(1:i)==prime);
end
output = [0:limit;FQN]'

Accumulate@ Array[Boole[FactorInteger[#][[-1, 1]] == 3] &, 80, 0] (* Michael De Vlieger, Apr 21 2018 *)

gpf(n) = if (n<=1, n, vecmax(factor(n)[,1]));
a(n) = sum(k=1, n, gpf(k)==3); \\ Michel Marcus, Mar 27 2018

From David A. Corneth, Mar 27 2018: (Start)
a(n) - a(n - 1) = 1 if and only if n is in 3 * A003586. If n isn't in that sequence then a(n) = a(n - 1).
a(3 * n + b) = A071521(n), n > 0, 0 <= b < 3. (End)
a(n) = A071521(n) - A070939(n). - Ridouane Oudra, Mar 24 2025

A069924 Number of k, 1<=k<=n, such that phi(k) divides k.

Original entry on oeis.org

1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15

Offset: 1

Benoit Cloitre, May 05 2002

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000
Vaclav Kotesovec, Plot of a(n)/log(n)^2 for n = 1..10000

Cf. A007694, A071521, A062153.

Table[Length[Select[Range[n], Divisible[#, EulerPhi[#]] &]], {n, 1, 100}] (* Vaclav Kotesovec, Feb 16 2019 *)
Accumulate[Table[If[Divisible[n,EulerPhi[n]],1,0],{n,80}]] (* Harvey P. Dale, Jul 04 2021 *)

for(n=1,150,print1(sum(i=1,n,if(i%eulerphi(i),0,1)),","))

a(n) = Card(k: 1<=k<=n : k==0 (mod phi(k))) asymptotically: a(n) = C*log(n)^2 + o(log(n)^2) with C=0.6....

a(n) = A071521(n) - A062153(n). - Ridouane Oudra, Mar 05 2025

A096067 Number of 3-smooth numbers between successive numbers that are powers of 2 or of 3.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 2, 0, 3, 1, 2, 4, 0, 5, 2, 3, 6, 0, 6, 5, 2, 8, 2, 6, 8, 1, 10, 4, 6, 11, 0, 11, 8, 4, 13, 3, 10, 12, 2, 15, 6, 9, 16, 0, 17, 9, 8, 18, 2, 16, 14, 5, 20, 6, 14, 19, 2, 22, 10, 12, 23, 1, 22, 16, 8, 25, 6, 19, 22, 4, 27, 11, 16, 28, 0, 29, 16, 13, 30, 4

Offset: 1

Reinhard Zumkeller, Jul 21 2004

a(n) = {k: A006899(n) < A003586(k) < A006899(n+1)}.

			n=16: there are three 3-smooth numbers between A006899(16)=3^6=729 and A006899(17)=2^10=1024: A003586(38)=2^8*3=768, A003586(39)=2^5*3^3=864 and A003586(40)=2^2*3^5=972, therefore a(16)=3.

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Cf. A003586, A006899, A071521.

spi[n_] := Sum[Floor@Log[2, n/3^k] + 1, {k, 0, Floor@Log[3, n]}];
seq[n_] := Module[{a = Table[0, {n}], p = 1, s = 1}, For[i = 1, i <= Length[a], i++, p = Min[2^(1 + Floor@Log[2, p]), 3^(1 + Floor@Log[3, p])]; With[{t = spi[p]}, a[[i]] = t - s - 1; s = t]]; a];
seq[100] (* Jean-François Alcover, Dec 17 2021, after Andrew Howroyd's PARI code *)

\\ here spi(n) is A071521(n).
spi(n)={sum(k=0, logint(n, 3), logint(n\3^k, 2)+1)}
seq(n)={my(a=vector(n), p=1, s=1); for(i=1, #a, p=min(2^(1+logint(p,2)), 3^(1+logint(p,3))); my(t=spi(p)); a[i]=t-s-1; s=t); a} \\ Andrew Howroyd, Jan 07 2020

Terms a(40) and beyond from Andrew Howroyd, Jan 06 2020

A179276 Largest 3-smooth number <= n.

Original entry on oeis.org

1, 2, 3, 4, 4, 6, 6, 8, 9, 9, 9, 12, 12, 12, 12, 16, 16, 18, 18, 18, 18, 18, 18, 24, 24, 24, 27, 27, 27, 27, 27, 32, 32, 32, 32, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 48, 48, 48, 48, 48, 48, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 64, 64, 64, 64, 64, 64, 64, 64, 72, 72

Offset: 1

Reinhard Zumkeller, Jul 07 2010

David A. Corneth, Table of n, a(n) for n = 1..10000

Cf. A003586, A065331, A065333, A081328, A071521.

smooth3Q[n_] := FactorInteger[n][[-1, 1]] <= 3;
a[n_] := For[k = n, True, k--, If[smooth3Q[k], Return[k]]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Oct 14 2021 *)

A065333(a(n)) = 1;
a(A003586(n)) = A003586(n);
A065331(n) <= a(n).
a(n) = A003586(A071521(n)). - Ridouane Oudra, Aug 24 2025

Definition corrected by Georg Fischer, Aug 05 2021

cp's OEIS Frontend

A100752 a(n) is the number of positive integers <= 10^n that are divisible by no prime exceeding 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A080786 Triangle T(n,k) = number of k-smooth numbers <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

A081063 Number of numbers <= n that are 3-smooth or prime powers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

A096300 Number of positive integers <= n with no prime factor > log(n).

Views

Author

Keywords

Links

Programs

Mathematica

PARI

Formula

A122256 Number of numbers <= n with 3-smooth Euler's totient (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A122258 Number of Pierpont primes <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301461 Number of integers less than or equal to n whose largest prime factor is 3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

Mathematica

PARI

Formula

A069924 Number of k, 1<=k<=n, such that phi(k) divides k.

Views

Author