7
$\begingroup$

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.

$\endgroup$

3 Answers 3

5
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ This is quite a long answer, but I've used as many clever tricks as possible to cut down on the amount of boring counting required. There may be another method which is altogether neater and doesn't involve any boring counting or multiplying at all (maybe binary representations would be useful?), but at least this works. BTW I haven't read Gareth's answer properly, so our methods may overlap somewhat. Ensuring no double-counting is what takes all the time in this one. $\endgroup$ May 6, 2020 at 13:46
  • $\begingroup$ For what it's worth, my program does give 616. In fact the first few values match this (with a shift) if it helps anyone find a less gruesome proof. $\endgroup$
    – Ankoganit
    May 6, 2020 at 15:31
  • $\begingroup$ @Daniel Must be a bug in your code then. You're missing 5, 15, 25, 29, 30, ... $\endgroup$ May 6, 2020 at 15:41
  • $\begingroup$ Not a bug in my code, but an error on my part. I was excluding n=0. Of course, non-negative does not mean positive. $\endgroup$ May 6, 2020 at 15:56
  • $\begingroup$ @Ankoganit Trying, but I keep coming back to the fact that according to that sequence for k=1 there are 4 integers, which is obviously impossible unless I'm reading that wrong. Probably should start elsewhere in the sequence. $\endgroup$
    – Quintec
    May 6, 2020 at 16:13
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ "Note that these various sets don't overlap one another" I don't think this is true, for example $69$ is both $16\cdot\text{OMF}-11$ and $2\cdot\text{OMF}-1$. $\endgroup$
    – Ankoganit
    May 6, 2020 at 5:10
  • 2
    $\begingroup$ The perils of trying to do mathematics after 3am. You are of course correct and I am of course a moron. I unfortunately need to be thinking about Other Things right now; it's not obvious to me whether this completely sinks the approach I took or whether it can be patched up... $\endgroup$
    – Gareth McCaughan
    May 6, 2020 at 10:09
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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