5
$\begingroup$

For example say, $n = 2$. So our set is $\{1, 2, 3, 4\}$ in base $10$ and $\{1, 10, 11, 100\}$ in base $2$. So Output $1$, because only one number i.e. $3$ is there such that it has $``11"$ in it.

For $n = 3$, we get $\{3, 6, 7\}$ as having $``11"$, so output $3$.

$\endgroup$
  • $\begingroup$ The binary representation will have at least $1$ and at most $n+1$ digits, the latter one being $2^n$. So count the appearances of $11$ in strings with length $\in \{2,...n\}$. $\endgroup$ – Alp Uzman Feb 9 '15 at 17:54
  • $\begingroup$ That will be so much computation. $\endgroup$ – user123 Feb 9 '15 at 17:56
  • $\begingroup$ Not really: for strings of $k$ digits there are $(k-1)!2^{k-2}$ for which $11$ appears at least once. $\endgroup$ – Alp Uzman Feb 9 '15 at 18:01
  • 1
    $\begingroup$ @Uzman: That formula is incorrect. For $k=3$ it gives $4$, but the correct number is $3$. $\endgroup$ – Brian M. Scott Feb 9 '15 at 18:04
  • $\begingroup$ Oh yes, my formula overcounts. Thanks. $\endgroup$ – Alp Uzman Feb 9 '15 at 18:07
4
$\begingroup$

$2^n$ does not. All of the other integers in the given range can be written as $n$-bit strings, with leading zeroes as needed. Thus, you want the number of $n$-bit strings that have two adjacent ones. It’s actually easier to count those that do not have two adjacent ones and subtract from $2^n$. That problem is solved in this question and answer: there are $F_{n+2}$ such sequences, where $F_n$ is the $n$-th Fibonacci number. The number that you want is therefore $2^n-F_{n+2}$.

The Fibonacci numbers are defined recursively, but the linked article gives closed forms. Perhaps the most convenient for computation is

$$F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor\;,$$

where $$\varphi=\frac{1+\sqrt5}2\;.$$

$\endgroup$
  • $\begingroup$ Thank you! (Characters limit... :p) $\endgroup$ – user123 Feb 9 '15 at 19:15
  • $\begingroup$ @user123: You’re welcome! $\endgroup$ – Brian M. Scott Feb 9 '15 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.