Skip to content

Sunday Times Teaser 3050 – Power Struggle

by BRG on March 5, 2021

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?

From → Uncategorized

15 Comments Leave one →
  1. Brian Gladman permalink

    • Frits permalink

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

      • Brian Gladman permalink

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

        • Frits permalink

          @Brian, I don’t exactly understand what you mean.

          You can at least reject odd dsq’s:

          • Brian Gladman permalink

            Yes I could do that, but I would have
            to explain why and its not worth it.

  2. Erling Torkildsen permalink

    Similarities with Brian’s approach, but rather slow I am afraid.

  3. Erling Torkildsen permalink

    A further improvement, I think. (Direct math)..

    Now corrected (see below).

    • Brian Gladman permalink

      Hi Erling, I made a couple of small changes to simplify it a bit. It’s certainly a lot faster than your first version.

    • Frits permalink

      @Erling, your dBN formula doesn’t seem to return correct values (f.i. n=363 then dBN = 149 while it should be 107).

      • Erling Torkildsen permalink

        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!

    • Erling Torkildsen permalink

      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.

  4. Frits permalink

  5. John Z permalink

    Nothing earth shattering:

  6. Frits permalink

    Variation of John’s program early rejecting specific x values.
    A “while” loop is used to manipulate the iterator.

Leave a comment to Brian Gladman Cancel reply

Note: HTML is allowed. Your email address will not be published.

Subscribe to this comment feed via RSS