cp's OEIS Frontend

A048623 Binary encoding of semiprimes (A001358).

%I A048623 #15 Feb 23 2025 11:15:29
%S A048623 2,3,4,5,9,6,10,17,8,33,18,65,12,129,34,257,16,66,20,130,513,1025,36,
%T A048623 258,2049,24,4097,68,8193,514,40,1026,16385,132,32769,2050,260,65537,
%U A048623 72,32,131073,4098,8194,136,262145,16386,524289,48,516,1048577,1028
%N A048623 Binary encoding of semiprimes (A001358).
%C A048623 Permutation of A048645 (without the term 1).
%H A048623 Michael De Vlieger, <a href="/A048623/b048623.txt">Table of n, a(n) for n = 1..10000</a>
%e A048623 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)
%p A048623 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.
%p A048623 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.
%p A048623 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;
%t A048623 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 *)
%o A048623 (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
%o A048623 (Python)
%o A048623 from math import isqrt
%o A048623 from sympy import primepi, primerange, factorint
%o A048623 def A048623(n):
%o A048623     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)))
%o A048623     m, k = n, f(n)
%o A048623     while m != k: m, k = k, f(k)
%o A048623     return sum(e<<primepi(p)-1 for p, e in factorint(m).items()) # _Chai Wah Wu_, Feb 22 2025
%Y A048623 Cf. A001358, A048639, A048672, A048645.
%K A048623 easy,nonn
%O A048623 1,1
%A A048623 _Antti Karttunen_, Jul 14 1999