login
A bijective binary representation of the prime factorization of a number, shown in decimal (see Comments for precise definition).
9

%I #29 Jan 02 2019 11:54:26

%S 0,1,2,4,8,3,16,32,64,5,128,6,256,9,10,512,1024,17,2048,12,18,33,4096,

%T 34,8192,65,16384,20,32768,7,65536,131072,66,129,24,36,262144,257,130,

%U 40,524288,11,1048576,68,72,513,2097152,258,4194304,1025,514,132

%N A bijective binary representation of the prime factorization of a number, shown in decimal (see Comments for precise definition).

%C For n > 0, with prime factorization Product_{i=1..k} p_i ^ e_i (all p_i distinct and all e_i > 0):

%C - let S_n = A000961 \ { p_i ^ (e_i + j) with i=1..k and j > 0 },

%C - a(n) = Sum_{i=1..k} 2^#{ s in S_n with 1 < s < p_i ^ e_i }.

%C In an informal way, we encode the prime powers > 1 that are unitary divisors of n as 1's in binary, while discarding the 0's corresponding to their "proper" multiples.

%C a(A002110(n)) = 2^n-1 for any n >= 0.

%C a(A000961(n+1)) = 2^(n-1) for any n > 0.

%C A000120(a(n)) = A001221(n) for any n > 0 (each prime divisor p of n (alongside the p-adic valuation of n) is encoded as a single 1 bit in the base-2 representation of a(n)).

%C A000961(2+A007814(a(n))) = A034684(n) for any n > 1 (the least significant bit of a(n) encodes the smallest unitary divisor of n that is larger than 1).

%C This sequence establishes a bijection between the positive numbers and the nonnegative numbers; see A289272 for the inverse of this sequence.

%C The numbers 4, 36, 40 and 532 equal their image; are there other such numbers?

%C This sequence has connections with A034729 (which encodes the divisors of a number, and is not surjective) and A087207 (which encodes the prime divisors of a number, and is not injective).

%H Rémy Sigrist, <a href="/A289271/b289271.txt">Table of n, a(n) for n = 1..10000</a>

%H Rémy Sigrist, <a href="/A289271/a289271.pdf">Illustration of the first terms</a>

%H Rémy Sigrist, <a href="/A289271/a289271.gp.txt">PARI program for A289271</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%e For n = 204 = 2^2 * 3 * 17:

%e - S_204 = A000961 \ { 2^3, 2^4, ..., 3^2, ... }

%e = { 1, 2, 3, 4, 5, 7, 11, 13, 17, ... },

%e - a(204) = 2^#{ 2, 3 } + 2^#{ 2 } + 2^#{ 2, 3, 4, 5, 7, 11, 13 }

%e = 2^2 + 2^1 + 2^7

%e = 134.

%e See also the illustration of the first terms in Links section.

%o (PARI) See Links section.

%o (PARI) A289271(n) = { my(f = factor(n), pps = vecsort(vector(#f~, i, f[i, 1]^f[i, 2])), s=0, x=1, pp=1, k=-1); for(i=1,#f~, while(pp < pps[i], pp++; while(!isprimepower(pp)||(gcd(pp,x)>1), pp++); k++); s += 2^k; x *= pp); (s); }; \\ _Antti Karttunen_, Jan 01 2019

%Y Cf. A000120, A000961, A001221, A002110, A007814, A034684, A034729, A087207, A289272 (inverse), A322988, A322990, A322991, A322992, A322995.

%Y Cf. also A156552, A052331 for similar constructions.

%K nonn,base

%O 1,3

%A _Rémy Sigrist_, Jun 30 2017