A297174 An auxiliary sequence for computing A300250. See comments and examples.

0, 1, 1, 5, 1, 19, 1, 69, 5, 19, 1, 2123, 1, 19, 19, 4165, 1, 2131, 1, 2125, 19, 19, 1, 4228171, 5, 19, 69, 2125, 1, 526631, 1, 2101317, 19, 19, 19, 268706123, 1, 19, 19, 4228237, 1, 526643, 1, 2125, 2123, 19, 1, 550026380363, 5, 2131, 19, 2125, 1, 4229203, 19, 4228237, 19, 19, 1, 8798249190555, 1, 19, 2123, 17181970501, 19, 526643, 1, 2125

Offset: 1

Author

Antti Karttunen, Mar 07 2018

Keywords

• nonn

Comments

In binary representation of a(n), the distances between successive 1's (one more than the lengths of intermediate 0-runs) from the right record the prime signature ranks (A101296) of successive divisors of n, as ordered from the smallest divisor (> 1) to the largest divisor (= n).

Examples

			a(1) = 0 by convention (as 1 has no prime divisors).
a(p) = 1 for any prime p.
For any n > 1, the least significant 1-bit is at rightmost position (bit-0), signifying the smallest prime factor of n, which is always the least divisor > 1.
For n = 4 = 2*2, the next divisor of 4 after 2 is 4, for which A101296(4) = 3, thus the second least significant 1-bit comes 3-1 = 2 positions left of the rightmost 1, thus a(4) = 2^0 + 2^(3-1) = 1+4 = 5.
For n = 6 with divisors d = 2, 3 and 6 larger than one, for which A101296(d)-1 gives 1, 1 and 3, thus a(6) = 2^(1-1) + 2^(1-1+1) + 2^(1-1+1+3) = 2^0 + 2^1 + 2^4 = 19.
For n = 12 with divisors d = 2, 3, 2*2, 2*3, 2*2*3 larger than one, A101296(d)-1 gives 1, 1, 2, 3 and 5 thus a(12) = 2^0 + 2^(0+1) + 2^(0+1+2) + 2^(0+1+2+3) + 2^(0+1+2+3+5) = 2123.
For n = 18 with divisors d = 2, 3, 2*3, 3*3, 2*3*3 larger than one, A101296(d)-1 gives 1, 1, 3, 2, and 5 thus a(18) = 2^0 + 2^(0+1) + 2^(0+1+3) + 2^(0+1+3+2) + 2^(0+1+3+2+5) = 2131.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..4096
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A101296, A300250 (restricted growth sequence transform of this sequence).

Cf. also A292258, A294897.

Programs

PARI

up_to = 4096;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523.
v101296 = rgs_transform(vector(up_to, n, A046523(n)));
A101296(n) = v101296[n];
A297174(n) = { my(s=0,i=-1); fordiv(n, d, if(d>1, i += (A101296(d)-1); s += 2^i)); (s); };