login
Restricted growth sequence computed for filter-sequence A278222, related to 1-runs in the binary representation of n.
62

%I #25 Jun 12 2018 10:17:45

%S 1,2,2,3,2,4,3,5,2,4,4,6,3,6,5,7,2,4,4,6,4,8,6,9,3,6,6,10,5,9,7,11,2,

%T 4,4,6,4,8,6,9,4,8,8,12,6,12,9,13,3,6,6,10,6,12,10,14,5,9,9,14,7,13,

%U 11,15,2,4,4,6,4,8,6,9,4,8,8,12,6,12,9,13,4,8,8,12,8,16,12,17,6,12,12,18,9,17,13,19,3,6,6,10,6,12,10,14,6,12,12,18,10,18

%N Restricted growth sequence computed for filter-sequence A278222, related to 1-runs in the binary representation of n.

%C When filtering sequences (by equivalence class partitioning), this sequence can be used instead of A278222, because for all i, j it holds that: a(i) = a(j) <=> A278222(i) = A278222(j).

%C For example, for all i, j: a(i) = a(j) => A000120(i) = A000120(j), and for all i, j: a(i) = a(j) => A001316(i) = A001316(j).

%C The sequence allots a distinct value for each distinct multiset formed from the lengths of 1-runs in the binary representation of n. See the examples. - _Antti Karttunen_, Jun 04 2017

%H Antti Karttunen, <a href="/A286622/b286622.txt">Table of n, a(n) for n = 0..65537</a>

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

%e For n = 0, there are no 1-runs, thus the multiset is empty [], and it is allotted the number 1, thus a(0) = 1.

%e For n = 1, in binary also "1", there is one 1-run of length 1, thus the multiset is [1], which has not been encountered before, and a new number is allotted for that, thus a(1) = 2.

%e For n = 2, in binary "10", there is one 1-run of length 1, thus the multiset is [1], which was already encountered at n=1, thus a(2) = a(1) = 2.

%e For n = 3, in binary "11", there is one 1-run of length 2, thus the multiset is [2], which has not been encountered before, and a new number is allotted for that, thus a(3) = 3.

%e For n = 4, in binary "100", there is one 1-run of length 1, thus the multiset is [1], which was already encountered at n=1 for the first time, thus a(4) = a(1) = 2.

%e For n = 5, in binary "101", there are two 1-runs, both of length 1, thus the multiset is [1,1], which has not been encountered before, and a new number is allotted for that, thus a(5) = 4.

%o (PARI)

%o rgs_transform(invec) = { my(occurrences = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(occurrences,invec[i]), my(pp = mapget(occurrences, invec[i])); outvec[i] = outvec[pp] , mapput(occurrences,invec[i],i); outvec[i] = u; u++ )); outvec; };

%o write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }

%o A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t }; \\ Modified from code of _M. F. Hasler_

%o A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ This function from _Charles R Greathouse IV_, Aug 17 2011

%o A278222(n) = A046523(A005940(1+n));

%o v286622 = rgs_transform(vector(1+65537, n, A278222(n-1)));

%o A286622(n) = v286622[1+n];

%Y Cf. A278222, A000120, A001316.

%Y Cf. A286552 (ordinal transform).

%Y Cf. also A101296, A286581, A286589, A286597, A286599, A286600, A286602, A286603, A286605, A286610, A286619, A286621, A286626, A286378, A304101 for similarly constructed or related sequences.

%Y Cf. also A305793, A305795.

%K nonn,look

%O 0,2

%A _Antti Karttunen_, May 11 2017

%E Example section added by _Antti Karttunen_, Jun 04 2017