A339690 Positive integers of the form 4^i*9^j*k with gcd(k,6)=1.

1, 4, 5, 7, 9, 11, 13, 16, 17, 19, 20, 23, 25, 28, 29, 31, 35, 36, 37, 41, 43, 44, 45, 47, 49, 52, 53, 55, 59, 61, 63, 64, 65, 67, 68, 71, 73, 76, 77, 79, 80, 81, 83, 85, 89, 91, 92, 95, 97, 99, 100, 101, 103, 107, 109, 112, 113, 115, 116, 117, 119, 121

Offset: 1

Author

Griffin N. Macris, Dec 13 2020, and Peter Munn, Feb 03 2021

Keywords

• nonn

Comments

Positive integers that survive sieving by the rule: if m appears then 2m, 3m and 6m do not.

Numbers whose squarefree part is congruent to 1 or 5 modulo 6.

Closed under multiplication.

Term by term, the sequence is one half of its complement within A007417, one third of its complement within A003159, and one sixth of its complement within A036668.

Asymptotic density is 1/2.

The set of all a(n) has maximal lower density (1/2) among sets S such that S, 2S, and 3S are disjoint.

Numbers which do not have 2 or 3 in their Fermi-Dirac factorization. Thus each term is a product of a unique subset of A050376 \ {2,3}.

It follows that the sequence is closed with respect to the commutative binary operation A059897(.,.), forming a subgroup of the positive integers considered as a group under A059897. It is the subgroup generated by A050376 \ {2,3}. A003159, A007417 and A036668 correspond to the nontrivial subgroups of its quotient group. It is the lexicographically earliest ordered transversal of the subgroup {1,2,3,6}, which in ordered form is the lexicographically earliest subgroup of order 4.

Examples

			Numbers are removed by the sieve only due to the presence of a smaller number, so 1 is in the sequence as the smallest positive integer. The sieve removes 2, as it is twice 1, which is in the sequence; so 2 is not in the sequence. The sieve removes 3, as it is three times 1, which is in the sequence, so 3 is not in the sequence. There are no integers m for which 3m = 4 or 6m = 4; 2m = 4 for m = 2, but 2 is not in the sequence; so the sieve does not remove 4, so 4 is in the sequence.
		

Links

• Jan Snellman, Greedy Regular Convolutions, arXiv:2504.02795 [math.NT], 2025.
• Eric Weisstein's World of Mathematics, Group.
• Eric Weisstein's World of Mathematics, Squarefree Part.
• Index entries for sequences generated by sieves

Crossrefs

Cf. A050376, A059897, A307150, A339746, A372574 (characteristic function).

Ordered first quadrisection of A052330.

Intersection of any 2 of A003159, A007417 and A036668.

A329575 divided by 3.

Programs

Mathematica

Select[Range[117], EvenQ[IntegerExponent[#, 2]] && EvenQ[IntegerExponent[#, 3]] &]
f[p_, e_] := p^Mod[e, 2]; core[n_] := Times @@ f @@@ FactorInteger[n]; Select[Range[121], CoprimeQ[core[#], 6] &] (* Amiram Eldar, Feb 06 2021 *)

PARI

isok(m) = core(m) % 6 == 1 || core(m) % 6 == 5;

Python

from itertools import count
from sympy import integer_log
def A339690(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c = n+x
        for i in range(integer_log(x,9)[0]+1):
            i2 = 9**i
            for j in count(0,2):
                k = i2<x:
                    break
                m = x//k
                c -= (m-1)//6+(m-5)//6+2
        return c
    return bisection(f,n,n) # Chai Wah Wu, Feb 14 2025

Formula

{a(n) : n >= 1} = {m : A307150(m) = 6m, m >= 0}.

{a(n) : n >= 1} = {k : k = A052330(4m), m >= 0}.

A329575(n) = a(n) * 3.

{A036668(n) : n >= 0} = {a(n) : n >= 1} U {6 * a(n) : n >= 1}.

{A003159(n) : n >= 1} = {a(n) : n >= 1} U {3 * a(n) : n >= 1}.

{A007417(n) : n >= 1} = {a(n) : n >= 1} U {2 * a(n) : n >= 1}.

a(n) ~ 2n.