login
Binary encoding of semiprimes (A001358).
8

%I #9 Oct 02 2015 08:58:45

%S 2,3,4,5,9,6,10,17,8,33,18,65,12,129,34,257,16,66,20,130,513,1025,36,

%T 258,2049,24,4097,68,8193,514,40,1026,16385,132,32769,2050,260,65537,

%U 72,32,131073,4098,8194,136,262145,16386,524289,48,516,1048577,1028

%N Binary encoding of semiprimes (A001358).

%C Permutation of A048645 (without the term 1).

%H Michael De Vlieger, <a href="/A048623/b048623.txt">Table of n, a(n) for n = 1..10000</a>

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

%Y Cf. A001358, A048639, A048672, A048645.

%K easy,nonn

%O 1,1

%A _Antti Karttunen_, Jul 14 1999