cp's OEIS Frontend

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

%I A297174 #16 Mar 08 2018 21:19:29
%S A297174 0,1,1,5,1,19,1,69,5,19,1,2123,1,19,19,4165,1,2131,1,2125,19,19,1,
%T A297174 4228171,5,19,69,2125,1,526631,1,2101317,19,19,19,268706123,1,19,19,
%U A297174 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
%N A297174 An auxiliary sequence for computing A300250. See comments and examples.
%C A297174 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).
%H A297174 Antti Karttunen, <a href="/A297174/b297174.txt">Table of n, a(n) for n = 1..4096</a>
%H A297174 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%e A297174 a(1) = 0 by convention (as 1 has no prime divisors).
%e A297174 a(p) = 1 for any prime p.
%e A297174 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.
%e A297174 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.
%e A297174 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.
%e A297174 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.
%e A297174 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.
%o A297174 (PARI)
%o A297174 up_to = 4096;
%o A297174 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; };
%o A297174 A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523.
%o A297174 v101296 = rgs_transform(vector(up_to, n, A046523(n)));
%o A297174 A101296(n) = v101296[n];
%o A297174 A297174(n) = { my(s=0,i=-1); fordiv(n, d, if(d>1, i += (A101296(d)-1); s += 2^i)); (s); };
%Y A297174 Cf. A101296, A300250 (restricted growth sequence transform of this sequence).
%Y A297174 Cf. also A292258, A294897.
%K A297174 nonn
%O A297174 1,4
%A A297174 _Antti Karttunen_, Mar 07 2018