A071521 Number of 3-smooth numbers <= n.

1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 10, 10, 10, 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,2

Comments

A 3-smooth number is a number of the form 2^x * 3^y where x >= 0 and y >= 0.

References

Bruce C. Berndt and Robert A. Rankin, "Ramanujan : letters and commentary", History of Mathematics Volume 9, AMS-LMS, p. 23, p. 35.

G. H. Hardy, Ramanujan: Twelve lectures on subjects suggested by his life and work, AMS Chelsea Pub., 1999, pages 67-82.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Thierry Bousch, La Tour de Stockmeyer, Séminaire Lotharingien de Combinatoire 77 (2017), Article B77d.

M. Haussman and H. N. Shapiro, On Ramanujan right triangle conjecture, Comm. Pure Appl. Math. 42 (1989), 885-889.

A. M. Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen, Abh. Math. Sem. Univ. Hamburg 1 (1922), 77-98; 250-251.

Raphael Schumacher, The Formulas for the Distribution of the 3-Smooth, 5-Smooth, 7-Smooth and all other Smooth Numbers, arXiv preprint arXiv:1608.06928 [math.NT], 2016.

Formula

a(n) = Card{ k | A003586(k) <= n }. Asymptotically: let a=1/(2*log(2)*log(3)), b=sqrt(6), then from Ramanujan a(n) ~ a*log(2*n)*log(3*n) or equivalently a(n) ~ a*log(b*n)^2.

A022331(n) = a(A000079(n)); A022330(n) = a(A000244(n)). - Reinhard Zumkeller, May 09 2006

a(n) = Sum_{k=1..n} mu(6k)*floor(n/k). - Benoit Cloitre, Jun 14 2007

a(n) = Sum_{k=1..n} (floor(6^k/k)-floor((6^k-1)/k)). - Anthony Browne, May 19 2016

From Ridouane Oudra, Jul 17 2020: (Start)

a(n) = Sum_{i=0..floor(log_2(n))} (floor(log_3(n/2^i)) + 1).

a(n) = Sum_{i=0..floor(log_3(n))} (floor(log_2(n/3^i)) + 1). (End)

A322026(n) = a(A065331(n)). - Antti Karttunen, Sep 08 2024

Maple

N:= 10000: # to get a(1) to a(N)
V:= Vector(N):
for y from 0 to floor(log[3](N)) do
  for x from 0 to ilog2(N/3^y) do
    V[2^x*3^y]:= 1
od od:
convert(map(round, Statistics:-CumulativeSum(V)), list); # Robert Israel, Dec 16 2014

Mathematica

a[n_] := Sum[ MoebiusMu[6k]*Floor[n/k], {k, 1, n}]; Table[a[n], {n, 1, 75}] (* Jean-François Alcover, Oct 11 2011, after Benoit Cloitre *)
f[n_] := Sum[Floor@Log[3, n/2^i] + 1, {i, 0, Log[2, n]}]; Array[f, 75] (* faster, or *)
f[n_] := Sum[Floor@Log[2, n/3^i] + 1, {i, 0, Log[3, n]}]; Array[f, 75] (* Robert G. Wilson v, Aug 18 2012 *)
Accumulate[Table[If[Max[FactorInteger[n][[All, 1]]]<4, 1, 0], {n, 80}]] (* Harvey P. Dale, Jan 11 2017 *)

Prog

(PARI) for(n=1, 100, print1(sum(k=1, n, if(sum(i=3, n, if(k%prime(i), 0, 1)), 0, 1)), ", "))
(PARI) a(n)=sum(k=1, n, moebius(2*3*k)*floor(n/k)) \\ Benoit Cloitre, Jun 14 2007
(PARI) a(n)=my(t=1/3); sum(k=0, logint(n, 3), t*=3; logint(n\t, 2)+1) \\ Charles R Greathouse IV, Jan 08 2018
(Haskell)
a071521 n = length $ takeWhile (<= n) a003586_list
-- Reinhard Zumkeller, Aug 14 2011
(Python)
from sympy import integer_log
def A071521(n): return sum((n//3**i).bit_length() for i in range(integer_log(n, 3)[0]+1)) # Chai Wah Wu, Sep 15 2024

Crossrefs

Cf. A003586.

Cf. A000079, A000244, A022330, A022331, A065331, A322026.

Sequence in context: A267530 A050292 A181627 * A204330 A225553 A039733

Adjacent sequences: A071518 A071519 A071520 * A071522 A071523 A071524

Keyword

easy,nice,nonn

Author

Benoit Cloitre, Jun 02 2002

Status

approved