A246716 Positive numbers that are not the product of (exactly) two distinct primes.

1, 2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 16, 17, 18, 19, 20, 23, 24, 25, 27, 28, 29, 30, 31, 32, 36, 37, 40, 41, 42, 43, 44, 45, 47, 48, 49, 50, 52, 53, 54, 56, 59, 60, 61, 63, 64, 66, 67, 68, 70, 71, 72, 73, 75, 76, 78, 79, 80, 81, 83, 84, 88, 89, 90, 92, 96, 97, 98, 99, 100

Offset: 1

Author

Giuseppe Coppoletta, Nov 01 2014

Keywords

• nonn
• easy

Comments

Non-disjoint union of A100959 and A000961. Disjoint union of A100959 and A001248.

Complement of A006881, then inheriting the "opposite" of the properties of A006881.

a(n+1) - a(n) <= 4 (gap upper bound) - (that is because among four consecutive integers there is always a multiple of 4, then there is a number which is not the product of two distinct primes). E.g., a(26)-a(25) = a(62)-a(61) = 4. Is it true that for any k <= 4 there are infinitely many numbers n such that a(n+1) - a(n) = k?

If r = A006881(n+1) - A006881(n) - 1 > 1, it indicates that there are r terms of (a(j)) starting with j = A006881(n) - n + 1 which are consecutive integers. E.g., A006881(8) - A006881(7) - 1 = 6, so there are 6 consecutive terms in (a(j)), starting with j = A006881(7) - 7 + 1 = 20.

Examples

			7 is a term because 7 is prime, so it has only one prime divisor.
8 and 9 are terms because neither of them has two distinct prime divisors.
30 is a term because it is the product of three primes.
But 35 is not a term because it is the product of two distinct primes.
		

Links

• Giuseppe Coppoletta, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001358, A100959, A006881, A007774, A001221, A001222, A007304, A000977, A001248, A000961.

Programs

Magma

[n: n in [1..100] | #PrimeDivisors(n) ne 2 or &*[t[2]: t in Factorization(n)] ne 1]; // Bruno Berselli, Nov 12 2014

Maple

filter:= n -> map(t -> t[2],ifactors(n)[2]) <> [1,1]:
select(filter, [$1..1000]); # Robert Israel, Nov 02 2014

Mathematica

Select[Range[125], Not[PrimeOmega[#] == PrimeNu[#] == 2] &] (* Alonso del Arte, Nov 03 2014 *)

PARI

isok(n) = (omega(n)!=2) || (bigomega(n) != 2); \\ Michel Marcus, Nov 01 2014

Python

from math import isqrt
from sympy import primepi, primerange
def A246716(n):
    def f(x): return int(n-(t:=primepi(s:=isqrt(x)))-(t*(t-1)>>1)+sum(primepi(x//k) for k in primerange(1, s+1)))
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    return bisection(f) # Chai Wah Wu, Aug 30 2024

Sage

def A246716_list(n) :
    R = []
    for i in (1..n) :
        d = prime_divisors(i)
        if len(d) != 2 or d[0]*d[1] != i : R.append(i)
    return R
A246716_list(100)

Sage

[n for n in (1..100) if sloane.A001221(n)!=2 or sloane.A001222(n)!=2] # Giuseppe Coppoletta, Jan 19 2015