Sunday Times Teaser 3050 – Power Struggle
by Victor Bryant
Published Sunday March 07 2021 (link)
Given any number, one can calculate how close it is to a perfect square or how close it is to a power of 2. For example, the number 7 is twice as far from its nearest perfect square as it is from its nearest power of 2. On the other hand, the number 40 is twice as far from its nearest power of 2 as it is from its nearest square.
I have quite easily found a larger number (odd and less than a million!) for which one of these distances is twice the other.
What is my number?
15 Comments
Leave one →
@Brian,
You can short circuit as nearest square must be odd (X is odd so distance between nearest power of 2 and X is always odd, so distance between nearest square and X must be even, so nearest square is odd)
@Frits.
I don’t think so since we are equating one distance with twice the other
and this can be either way round.
Edit: My apologies, your analysis is right. But I can’t make use of that
because I’m bisecting the list and if the even squares are not present
the logic goes wrong.
@Brian, I don’t exactly understand what you mean.
You can at least reject odd dsq’s:
Yes I could do that, but I would have
to explain why and its not worth it.
Similarities with Brian’s approach, but rather slow I am afraid.
A further improvement, I think. (Direct math)..
Now corrected (see below).
Hi Erling, I made a couple of small changes to simplify it a bit. It’s certainly a lot faster than your first version.
@Erling, your dBN formula doesn’t seem to return correct values (f.i. n=363 then dBN = 149 while it should be 107).
Thanks Frits. As you see, it is based on rounding, and so an element of
chance will be involved. I shall have to test it, after I night’s sleep.
Exiting to have a look of its statistics!
Frits pointed to a fatal flaw in my late programme. A simple test showed that the nearest power of 2 was correctly found only in 91 % of cases.
By first aid from Brian, it seems that its basic idea still can prevail.
Nothing earth shattering:
Variation of John’s program early rejecting specific x values.
A “while” loop is used to manipulate the iterator.
@Brian, I’ll send an unscrambled version.