A339690 - OEIS

%I #53 Feb 16 2025 08:34:01

%S 1,4,5,7,9,11,13,16,17,19,20,23,25,28,29,31,35,36,37,41,43,44,45,47,

%T 49,52,53,55,59,61,63,64,65,67,68,71,73,76,77,79,80,81,83,85,89,91,92,

%U 95,97,99,100,101,103,107,109,112,113,115,116,117,119,121

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

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

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

%C Closed under multiplication.

%C 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.

%C Asymptotic density is 1/2.

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

%C 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}.

%C 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.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Group.html">Group</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SquarefreePart.html">Squarefree Part</a>.

%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>

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

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

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

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

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

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

%F a(n) ~ 2n.

%e 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.

%t Select[Range[117], EvenQ[IntegerExponent[#, 2]] && EvenQ[IntegerExponent[#, 3]] &]

%t f[p_, e_] := p^Mod[e, 2]; core[n_] := Times @@ f @@@ FactorInteger[n]; Select[Range[121], CoprimeQ[core[#], 6] &] (* _Amiram Eldar_, Feb 06 2021 *)

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

%o (Python)

%o from itertools import count

%o from sympy import integer_log

%o def A339690(n):

%o     def bisection(f,kmin=0,kmax=1):

%o         while f(kmax) > kmax: kmax <<= 1

%o         kmin = kmax >> 1

%o         while kmax-kmin > 1:

%o             kmid = kmax+kmin>>1

%o             if f(kmid) <= kmid:

%o                 kmax = kmid

%o             else:

%o                 kmin = kmid

%o         return kmax

%o     def f(x):

%o         c = n+x

%o         for i in range(integer_log(x,9)[0]+1):

%o             i2 = 9**i

%o             for j in count(0,2):

%o                 k = i2<<j

%o                 if k>x:

%o                     break

%o                 m = x//k

%o                 c -= (m-1)//6+(m-5)//6+2

%o         return c

%o     return bisection(f,n,n) # _Chai Wah Wu_, Feb 14 2025

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

%Y Ordered first quadrisection of A052330.

%Y Intersection of any 2 of A003159, A007417 and A036668.

%Y A329575 divided by 3.

%K nonn,changed

%O 1,2

%A _Griffin N. Macris_, Dec 13 2020, and _Peter Munn_, Feb 03 2021