A071604 a(n) is the number of 7-smooth numbers <= n.

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

Offset: 1

Author

Benoit Cloitre, Jun 02 2002

Keywords

• nonn
• easy

Comments

A 7-smooth number is a number of the form 2^x*3^y*5^z*7^u, (x,y,z,u) >= 0.

In other words, a 7-smooth number is a number with no prime factor greater than 7. - Peter Munn, Nov 20 2021

Examples

			a(11) = 10 as there are 10 7-smooth numbers <= 11. Namely 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. - _David A. Corneth_, Apr 19 2021
		

Links

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

Crossrefs

Partial sums of A086299.

Column 7 of A080786.

Cf. A002473, A106600, A343598.

Equivalent sequences with other limits on greatest prime factor: A070939 (2), A071521 (3), A071520 (5), A071523 (11), A080684 (13), A080685 (17), A080686 (19), A096300 (log n).

Programs

PARI

for(n=1,100,print1(sum(k=1,n,if(sum(i=5,n,if(k%prime(i),0,1)),0,1)),","))

Python

from sympy import integer_log
def A071604(n):
    c = 0
    for i in range(integer_log(n,7)[0]+1):
        i7 = 7**i
        m = n//i7
        for j in range(integer_log(m,5)[0]+1):
            j5 = 5**j
            r = m//j5
            for k in range(integer_log(r,3)[0]+1):
                c += (r//3**k).bit_length()
    return c # Chai Wah Wu, Sep 16 2024

Formula

a(n) = Card{ k | A002473 (k) <= n }.

Extensions

Name corrected by David A. Corneth, Apr 19 2021