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

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

Offset: 0

Author

Antti Karttunen, May 11 2017

Keywords

• nonn
• look

Comments

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

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

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

Examples

			For n = 0, there are no 1-runs, thus the multiset is empty [], and it is allotted the number 1, thus a(0) = 1.
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.
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.
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.
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.
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.
		

Links

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

Crossrefs

Cf. A278222, A000120, A001316.

Cf. A286552 (ordinal transform).

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

Cf. also A305793, A305795.

Programs

PARI

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; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
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
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
A278222(n) = A046523(A005940(1+n));
v286622 = rgs_transform(vector(1+65537, n, A278222(n-1)));
A286622(n) = v286622[1+n];

Extensions

Example section added by Antti Karttunen, Jun 04 2017