login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A161822 a(n) = the smallest positive integer such that both n and a(n), when represented in binary, contain the same types of runs of 0's, the runs being in any order. 5
1, 2, 1, 4, 2, 2, 1, 8, 4, 10, 2, 4, 2, 2, 1, 16, 8, 18, 4, 18, 10, 10, 2, 8, 4, 10, 2, 4, 2, 2, 1, 32, 16, 34, 8, 36, 18, 18, 4, 34, 18, 42, 10, 18, 10, 10, 2, 16, 8, 18, 4, 18, 10, 10, 2, 8, 4, 10, 2, 4, 2, 2, 1, 64, 32, 66, 16, 68, 34, 34, 8, 68, 36, 74, 18, 36, 18, 18, 4, 66, 34, 74, 18 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Clarification of definition: Think of binary n and a(n) each as a string of 0's and 1's. Consider the "runs" of 0's in binary n and a(n), where each run is made up completely of 0's, and is bounded on both sides either by 1's or by the edge of the string. Now consider the lengths of each bounded run of 0's (the number of 0's in each run). Then a(n) is the smallest positive integer whose set of run-lengths is a permutation of the set of run-lengths for n. (See example.)

1 <= a(n) <= n. a(n) = n iff n = 2^m for some m. a(n) = 1 iff n = 2^m - 1 for some m. - Hagen von Eitzen, Jun 22 2009

LINKS

Michael De Vlieger, Table of n, a(n) for n = 1..10000

EXAMPLE

84 in binary is 1010100. There are three runs of 0's, two runs of one 0 each and one run of two 0's. So we are looking for the smallest positive integer with two runs of one 0 each and one run of two 0's (and no other runs of 0's). For example, 16 in binary is 10000, which contains the runs, except that it is required that each run be bounded by 1's or the edge of the binary string. The next number that fits the requirements completely is 74 = 1001010 in binary. So a(84) = 74.

MATHEMATICA

f[n_] := Sort@ Map[Length, Select[Split@ IntegerDigits[n, 2], First@ # == 0 &]]; Table[Block[{k = 1}, While[f@ k != f@ n, k++]; k], {n, 83}] (* Michael De Vlieger, Aug 31 2017 *)

PROG

(PARI) a(n)=local(B=binary(n), L=[], ct=0); forstep(i=#B, 1, -1, if(B[i], if(ct, L=concat(L, ct); ct=0), ct++)); L=vecsort(L); forstep(i=#L, 1, -1, ct=(ct*2+1)*2^L[i]); if(ct>0, ct, 1) \\ Hagen von Eitzen, Jun 22 2009

CROSSREFS

Cf. A161819, A161820, A161821.

Sequence in context: A109090 A220780 A080100 * A001176 A136693 A086685

Adjacent sequences:  A161819 A161820 A161821 * A161823 A161824 A161825

KEYWORD

base,nonn

AUTHOR

Leroy Quet, Jun 20 2009

EXTENSIONS

More terms from Hagen von Eitzen, Jun 22 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 04:29 EST 2018. Contains 318049 sequences. (Running on oeis4.)