A048623 Binary encoding of semiprimes (A001358).

2, 3, 4, 5, 9, 6, 10, 17, 8, 33, 18, 65, 12, 129, 34, 257, 16, 66, 20, 130, 513, 1025, 36, 258, 2049, 24, 4097, 68, 8193, 514, 40, 1026, 16385, 132, 32769, 2050, 260, 65537, 72, 32, 131073, 4098, 8194, 136, 262145, 16386, 524289, 48, 516, 1048577, 1028

Offset: 1

Author

Antti Karttunen, Jul 14 1999

Keywords

• easy
• nonn

Comments

Permutation of A048645 (without the term 1).

Examples

			Squares p_i^2 are encoded with a single bit in position i (e.g. 25=ithprime(3)*ithprime(3) => 2^3 = 8) and other terms p_i*p_j are encoded with two bits, as sum 2^(i-1)+2^(j-1)
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001358, A048639, A048672, A048645.

Programs

Maple

nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc.
bef := proc(n) local s,d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end; # bef = Binary Encode Factorization.
encode_semiprimes := proc(upto_n) local b,i; b := [ ]; for i from 1 to upto_n do if((3 = tau(i)) or ((0 <> mobius(i)) and (4 = tau(i)))) then b := [ op(b), bef(i) ]; fi; od: RETURN(b); end;

Mathematica

f[n_] := Block[{p = FactorInteger@ n}, Total[2^PrimePi@ # &@ Map[First, p - If[Length@ p == 2, 1, 0]]]]; f /@ Select[Range@ 156, PrimeOmega@ # == 2 &] (* Michael De Vlieger, Oct 01 2015 *)

PARI

lista(nn) = {for (n=1, nn, if (bigomega(n)==2, if (issquare(n), x = 2^primepi(sqrtint(n)), f = factor(n); x = sum(k=1, #f~, 2^(primepi(f[k,1]) - 1))); print1(x, ", ");););} \\ Michel Marcus, Oct 02 2015

Python

from math import isqrt
from sympy import primepi, primerange, factorint
def A048623(n):
    def f(x): return int(n+x+((t:=primepi(s:=isqrt(x)))*(t-1)>>1)-sum(primepi(x//p) for p in primerange(s+1)))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return sum(e<Chai Wah Wu, Feb 22 2025