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,4

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).

Links

Antti Karttunen, Table of n, a(n) for n = 1..4096

Index entries for sequences related to binary expansion of n

Example

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.

Prog

(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); };

Crossrefs

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

Cf. also A292258, A294897.

Sequence in context: A326121 A008971 A151335 * A226605 A055584 A193861

Adjacent sequences: A297171 A297172 A297173 * A297175 A297176 A297177

Keyword

nonn

Author

Antti Karttunen, Mar 07 2018

Status

approved