The ceiling function and powers of 2

Question

How many integers $1\le x\le2048$ such that $$\Big\lceil \frac x{2^n}\Big\rceil$$ is not a multiple of five for all nonnegative integers $n$?

This problem is a 2020 contest problem which has finished.

Answer 1

Clearly, every power of 2 is a number $x$ as desired. That gives 13 possible $x$ right away.

Now let $2^k<x<2^{k+1}$, where $k\leq10$, and consider possible values of $n$. We'll seek the opposite of what was asked for, namely all $x$ such that some $\lceil\frac{x}{2^n}\rceil$ is a multiple of 5.

• If $n\geq k-1$, then $\frac{x}{2^n}<4$ so its ceiling cannot be a multiple of 5.

  The above is for all $k$, but in particular this means

  no possibilities for $k=0,1$.

• If $n=k-2$, then $4<\frac{x}{2^n}<8$, so all numbers $x$ such that $x\leq2^{k-2}5$ are included.

  The above is for all $k$, but in particular this means

  just one possibility for $k=2$ (namely $x=5$).

• If $n=k-3$, then $8<\frac{x}{2^n}<16$, so all numbers $x$ such that $2^{k-3}9<x\leq2^{k-3}10$ or $2^{k-3}14<x\leq2^{k-3}15$ are included. The first of these is already covered by the previous thing $x\leq2^{k-2}5$, so to avoid redundancy, $\frac{x}{2^{k-3}}$ is EITHER $\leq10$ OR in $(14,15]$.

  The above is for all $k$, but in particular this means

  three possibilities for $k=3$ (namely $9,10$ and $15$).

• If $n=k-4$, then $16<\frac{x}{2^n}<32$, and the cases $\frac{x}{2^{k-4}}$ being $\leq20$ or in $(28,30]$ are already covered, so we just need to cover $(24,25]$.

  The above is for all $k$, but in particular this means

  seven possibilities for $k=4$ (namely $17,18,19,20$; $29,30$ and $25$).

• If $n=k-5$, then $32<\frac{x}{2^n}<64$, and the cases $\frac{x}{2^{k-5}}$ being $\leq40$ or in $(48,50]$ or in $(56,60]$ are already covered, so we just need to cover $(44,45]$ and $(54,55]$.

  The above is for all $k$, but in particular this means

  sixteen possibilities for $k=5$ (double the previous plus two more).

• If $n=k-6$, then $64<\frac{x}{2^n}<128$, and the cases $\frac{x}{2^{k-6}}$ being $\leq80$ or in $(88,90]$ or in $(96,100]$ or in $(108,110]$ or in $(112,120]$ are already covered, so we just need to cover $(84,85]$ and $(94,95]$ and $(104,105]$ and $(124,125]$.

  The above is for all $k$, but in particular this means

  thirty-six possibilities for $k=6$ (double the previous plus four more).

• If $n=k-7$, then $128<\frac{x}{2^n}<256$, and the cases $\frac{x}{2^{k-7}}$ being $\leq160$ or in $(168,170]$ or in $(176,180]$ or in $(188,190]$ or in $(192,200]$ or in $(208,210]$ or in $(216,220]$ or in $(224,240]$ or in $(248,250]$ are already covered, so we just need to cover $(164,165]$ and $(174,175]$ and $(184,185]$ and $(204,205]$ and $(214,215]$ and $(244,245]$ and $(254,255]$.

  The above is for all $k$, but in particular this means

  seventy-nine possibilities for $k=7$ (double the previous plus seven more).

• If $n=k-8$, then $256<\frac{x}{2^n}<512$, and the cases $\frac{x}{2^{k-8}}$ being $\leq320$ or in $(328,330]$ or in $(336,340]$ or in $(348,350]$ or in $(352,360]$ or in $(368,370]$ or in $(376,380]$ or in $(384,400]$ or in $(408,410]$ or in $(416,420]$ or in $(428,430]$ or in $(432,440]$ or in $(448,480]$ or in $(496,500]$ or in $(508,510]$ are already covered, so we just need to cover intervals of length one for $325,335,345$, $365,375$, $405,415,425$, $445$, $485,495,505$ (at the next steps these will become intervals of length two or four and not cover any extra multiples of 5).

  The above is for all $k$, but in particular this means

  a hundred and seventy possibilities for $k=8$ (double the previous plus twelve more).

• If $n=k-9$, then $512<\frac{x}{2^n}<1024$, and the cases $\frac{x}{2^{k-9}}$ being $\leq640$ or in $(656,660]$ or in $(672,680]$ or in $(696,700]$ or in $(704,720]$ or in $(736,740]$ or in $(752,760]$ or in $(768,800]$ or in $(816,820]$ or in $(832,840]$ or in $(856,860]$ or in $(864,880]$ or in $(896,960]$ or in $(992,1000]$ or in $(1016,1020]$ and all other even multiples of $5$ are already covered, so we just need to cover intervals of length one for $645,655,665$, $685,695$, $725,735,745$, $765$, $805,815,825$, $845,855$, $885,895$, $965,975,985$, $1005,1015$ (at the next step these will become intervals of length two and not cover any extra multiples of 5).

  The above is for all $k$, but in particular this means

  three hundred and sixty-one possibilities for $k=9$ (double the previous plus twenty-one more).

• Finally, if $n=k-10$, then $1024<\frac{x}{2^n}<2048$, and the cases $\frac{x}{2^{k-9}}$ being $\leq1280$ or in $(1312,1320]$ or in $(1344,1360]$ or in $(1392,1400]$ or in $(1408,1440]$ or in $(1472,1480]$ or in $(1504,1520]$ or in $(1532,1600]$ or in $(1632,1640]$ or in $(1664,1680]$ or in $(1712,1720]$ or in $(1728,1760]$ or in $(1792,1920]$ or in $(1984,2000]$ or in $(2032,2040]$ and all other even multiples of $5$ are already covered, so we just need to cover intervals of length one for $1285,1295,1305$, $1325,1335$, $1365,1375,1385$, $1405$, $1445,1455,1465$, $1485,1495$, $1525$, $1605,1615,1625$, $1645,1655$, $1685,1695,1705$, $1725$, $1765,1775,1785$, $1925,1935,1945,1955,1965,1975$, $2005,2015,2025$, $2045$.

  The above is for all $k$, but in particular this means

  seven hundred and fifty-nine possibilities for $k=10$ (double the previous plus thirty-seven more).

So the total number of possibilities counted here is

$1+3+7+16+36+79+170+361+759=1432$,

and the final answer is

$2048-1432=616$.

Answer 2

Wrong answer

(Ankoganit correctly points out in comments that one claim I made is entirely untrue. I'm not sure whether this means that the whole approach is unfixably wrong. I need to be thinking about other things right now; if it turns out that this can be patched up then I hope other solvers will feel free to post patched-up versions.)

---

Let's ask instead

how many $x$ there are for which one of those numbers is a multiple of 5. If that's so, then one of them is more specifically an odd multiple of 5, so let's now look at the smallest $n$ for which $\lceil\frac x{2^n}\rceil$ is an odd multiple of 5. This is true for $n=0$ if $x$ itself is an odd multiple of 5; let's write $x=\textrm{OMF}$ for short. It's true for $n=1$ if $x=2\cdot\textrm{OMF}$ or $x=2\cdot\textrm{OMF-1}$; for $n=2$ if $x=4\cdot\textrm{OMF}-\{0,1,2,3\}$; and so forth. Note that these various sets don't overlap one another.

So

each multiple of 5 contributes a number of "bad" values of $x$ equal to the largest power of 2 dividing it, for a sum that looks like $1+2+1+4+1+2+1+8+\cdots$ for $5,10,15,20,25,30,35,40,\dots$. The number of odd multiples of 5 up to $n$ is $\lfloor\frac{n+5}{10}\rfloor$, and hence the number of multiples of 5 divisible by exactly $2^k$ is $\lfloor\frac{2^{-k}n+5}{10}\rfloor$, so the number of "bad" $x$ up to $2048=2^11$ is $\sum_k\lfloor\frac{2^{11-k}+5}{10}\rfloor2^k$. That is: $\frac{2048+5}{10}+\frac{1024+5}{10}+\frac{512+5}{10}+\cdots+\frac{2+5}{10}+\frac{1+5}{10}$ which equals $205\cdot1+102\cdot2+51\cdot4+26\cdot8+13\cdot16+6\cdot32+3\cdot64+2\cdot128+1\cdot256+0+0+0$ or 205+204+204+208+208+192+192+256+256=1925, leaving 123 values of $x$ for which none of those powers of 2 works out.

If the answer to this question actually mattered then I would check by brute-force computer calculation, but that is forbidden by the no-computers tag. There is therefore something like an 80% chance that there is at least one boneheaded error in the calculations above that makes the specific answer I gave incorrect.

(I suspect there's a more elegant argument available, with slightly more cunning counting, but it's nearly 4am local time so I'm not going to try to find one.)

Answer 3

Here's a slightly quicker way to count it (similar to Rand, I think)

All the numbers $x$ for which $\lceil \frac{x}{2^n} \rceil$ is divisible by $5$ for some $n$ are precisely those of the form $$2^k y - z $$ where $y$ is a positive integer divisible by $5$, $k \geq 0$ and $0 \leq z \leq 2^{k}-1$.
If we consider $S_m$ to be the set of such numbers between $1$ and $2^m$ then, $S_{m+1}$ is $T_m = \{x, 2x, 2x-1 | x \in S_m\}$ together with any new numbers divisible by $5$.
If we let $W_{m+1}$ be the set of numbers in $S_{m+1}$ which are not in $T_m$ then we see that each member of $W_{m}$ begins a new chain of numbers (through operations $2x$ and $2x-1$) which will have a total size of $2^{12-m} -1$ below $2048$.
For example, $5$ generates $511$ numbers in this way,
$15$ generates $255$,
$25$ generates $127$,
$(45,55)$ both generate $63$,
$(95,95,105,125)$ generate $31$ each,
$(165,175,185,205,215,245,255)$ each generate $15$,
$(325,335,345,365,375,405,415,425,445,485,495,505)$ each generate $7$,
$(645,655,665,685,695,725,735,745,765,805,815,825,845,855,885,895,965,975,985,1005,1015)$ each generate $3$ and the remaining ungenerated numbers are
$(1285,1295,1305,1325,1335,1365,1375,1385,1405,1445,1455,1465,1485,1495,1525,1605,1615,1625,1645,1655,1685,1695,1705,1725,1765,1775,1785,1925,1935,1945,1955,1965,1975, 2005,2015,2025,2045)$.
So the total is $$511 + 255 + 127 + (2 \times 63) + (4 \times 31) + (7 \times 15) + (12 \times 7) + (21 \times 3) + 37 = 1432$$ which means the answer must be $$ 2048 - 1432 = 616$$