3
$\begingroup$

How many positive integers n are there such that all of the following take place:

1) n has 1000 digits.

2) all of the digits are odd.

3) the absolute value of the difference of any two consecutive (neighboring) digits is equal to 2.

Please help. I don’t even know how to start.

$\endgroup$
  • $\begingroup$ Start with an easier problem: how many two-digit numbers are there? what about three-digit? $\endgroup$ – Vasya Apr 18 at 18:42
  • $\begingroup$ I could simply guess the case of two digit numbers. How does it help me prove the general one? $\endgroup$ – furfur Apr 18 at 18:53
  • $\begingroup$ You do not need to guess, you can count. How many choices for the first digit do you have? what about the second? $\endgroup$ – Vasya Apr 18 at 19:08
  • $\begingroup$ For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this. $\endgroup$ – furfur Apr 18 at 19:11
  • 2
    $\begingroup$ Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}\qquad \text{for all }m\ge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it. $\endgroup$ – Mike Earnest Apr 18 at 20:30
3
$\begingroup$

The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boil down to a very simple final answer for $n\ge2$: $$a_n=\begin{cases}\hphantom18\cdot 3^{\frac{n-2}2},& n\text{ even},\\14 \cdot 3^{\frac{n-3}2},& n\text{ odd}.\end{cases}\tag1$$

The most simple way to prove $(1)$ is to count directly the number of ways for the cases $n=2,3,4,5$ obtaining $a_n=8,14,24,42$, and then proceed by induction applying the recurrence relation suggested by Mike Earnest on the base of the characteristic polynomial of the matrix introduced by Julian Mejia: $$ a_n=4a_{n-2}-3a_{n-4}.\tag2 $$

In fact the simplicity of the answer suggests that there is possibly a simpler way to prove $(2)$ or even directly $(1)$.

$\endgroup$
2
$\begingroup$

Define $n_i=2i-1$ (so a bijection between 1,2,3,4,5 with 1,3,5,7,9). Consider the 5x5 matrix $A=(a_{i,j})$ with $a_{i,j}=1$ if $n_i$ and $n_j$ differ by 2 and $a_{i,j}=0$ otherwise. Then, the number of positive integers with "m" digits satisfying your properties is the sum of entries of $A^{m-1}$. So you want to find the sum of entries of $A^{999}$. I don't know if this is easy to compute without computers.

Edit: We have $$A=\left(\begin{array}{ccccc} 0&1&0&0&0\\ 1&0&1&0&0\\ 0&1&0&1&0\\ 0&0&1&0&1\\ 0&0&0&1&0\\ \end{array} \right)$$ So, thanks to @Mike's comment, it shouldn't be difficult to find the entries of $A^{999}$ we have that $A=PDP^{-1}$ with

$$D=\left(\begin{array}{ccccc} -1&0&0&0&0\\ 0&0&0&0&0\\ 0&0&1&0&0\\ 0&0&0&-\sqrt{3}&0\\ 0&0&0&0&\sqrt{3}\\ \end{array} \right)$$

$$P=\left(\begin{array}{ccccc} -1&1&-1&1&1\\ 1&0&-1&-\sqrt{3}&\sqrt{3}\\ 0&-1&0&2&2\\ -1&0&1&-\sqrt{3}&\sqrt{3}\\ 1&1&1&1&1\\ \end{array} \right)$$ So, we can compute $A^{999}=PD^{999}P^{-1}$ whose entries will be a linear combination of $(-1)^{999}, (1)^{999}, (-\sqrt{3})^{999},(\sqrt{3})^{999}$.

$\endgroup$
  • 1
    $\begingroup$ It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $\lambda^5-4\lambda^3+3\lambda=\lambda(\lambda^2-1)(\lambda^2-3)$, etc. $\endgroup$ – Mike Earnest Apr 18 at 20:12
1
$\begingroup$

Here is a OCaml program that computes the number of numbers in term of the size of the number:

type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)


let hdStr (s: 'a stream) : 'a =
  match s with
  | Eos -> failwith "headless stream"
  | StrCons (x,_) -> x;;

let tlStr (s : 'a stream) : 'a stream =
  match s with
  | Eos -> failwith "empty stream"
  | StrCons (x, t) -> t ();;    



let rec listify (s : 'a stream) (n: int) : 'a list =
  if n <= 0 then []
  else
    match s with
    | Eos -> []
    | _ -> (hdStr s) :: listify (tlStr s) (n - 1);;

let rec howmanynumber start step=
  if step = 0 then 1 else
    match start with
    |1->howmanynumber 3 (step-1)
    |3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
    |5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
    |7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
    |9->howmanynumber 7 (step-1) 
    |_->failwith "exception error"



let count n=
  (howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)

let rec thisseq  n = StrCons(count n , fun ()-> thisseq (n+1))

let result = thisseq 1

So Based on @Julian solution, the answer is the sum of entries of

$\begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}^{999} * \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ \end{bmatrix}$

$\endgroup$
  • $\begingroup$ Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though! $\endgroup$ – furfur Apr 18 at 19:26

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.