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

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

Author

Ralph-Joseph Tatt, Mar 21 2018

Keywords

• nonn

Comments

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.

Examples

			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.
		

Crossrefs

Cf. A003586, A065119, A071521.

Cf. A301506, A071521, A070939.

Programs

MATLAB

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]'

Mathematica

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

PARI

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

Formula

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