Skip to content
March 10, 2011 / steve8

Number in a haystack

 

Last month’s ponder-this puzzle caught my eye, so I decided to give it a whirl.

in short, its to find an integer n which has 3 properties:

A: n is flippable and flip( n) = n

B: n*n is flippable

C: n is divisible by 2011

where the flip of an integer, is the number that appears when the decimal representation in old style 7-segment font is rotated 180 degrees.

I will walk through how my solution evolved.

We could just increment integers, checking each one for all 3 conditions, and the easiest shortcut that seems obvious is to increment by 2011, (only checking numbers that satisfy condition C).  Let’s look at the code that does this:

import time

def flip(n):
    if n in ["0","1","2","5","8"]:
        return n
    if n == "6":
        return "9"
    if n == "9":
        return "6"
    return False

def flippable(z):
    for s in str(z):
        if s in ["3","4","7"]:
            return False
    return True

def flipnisn(z):
    strz = str(z)
    lenz = len(strz)
    for y in range(0,int(lenz/2)):
        if flip(strz[y]) != strz[lenz-y-1]:
            return False
    return True

t0 = time.time()
x=0
add = 2011
while True:
    x+=add
    if flippable(x):
        if flipnisn(x):
            if flippable(x*x):
                print(str(x)+ " is flippable")
                print("flip("+str(x)+") = " + str(x))
                print("n^2 = "+str(x**2)+" is flippable")
                break
print(str(int(time.time() - t0)) + " seconds")

output:

 

5000261920005 is flippable
flip(5000261920005) = 5000261920005
n^2 = 25002619268652089019200025 is flippable
2073 seconds

This is simple and condense, but uses lots of conversions between integers and their string representations to the individual digits of the base10 integer.

Imagine a 20 digit decimal integer, for the vast majority of multiples of 2011, from one to the next only 4 digits actually change, so it’s silly to convert the entire integer each time to a string to check for flippability conditions.

Using a list of digits as the base-10 representation of the number, adding 2011 each iteration, and having the logic to do the carry-over properly when necessary… while it may be extra code, and will likely be slower for small numbers, will at some point prove better as the number of digits in the integer is large compared to 4.

lets look at an implementation:

import time
def flip(n):
    if n in [0,1,2,5,8]:
        return n
    if n == 6:
        return 9
    if n == 9:
        return 6
    return False

def int2list(z):
    n = []
    while z!=0:
        n.append(z%10)
        z = int(z/10)
    return n

def add2list(listx,add):
    again = True
    i=0
    lenadd = len(add)
    while again:
        again = False
        if lenadd>i:
            listx[i]+=add[i]
            if lenadd>i+1:
                again = True

        if listx[i]>9:
            if len(listx)<=i+1:
                listx.append(int(listx[i]/10))
            else:
                listx[i+1]+=int(listx[i]/10)
                if listx[i+1]>9:
                    again = True
            listx[i] = listx[i]%10
        i+=1
    return

def flippable(z):
    for d in z:
        if d in [3,4,7]:
            return False
    return True

def flipnisn(z):
    lenz=len(z)
    for y in range(0,lenz):
        if flip(z[y]) != z[lenz-y-1]:
            return False
    return True

t0 = time.time()
add = 2011
listx = int2list(add)
addlist = int2list(add)
for n in range(2,10**20):
    add2list(listx,addlist)
    if flippable(listx):
        if flipnisn(listx):
            x=n*add
            if flippable(int2list(x**2)):
                print(str(x)+ " is flippable")
                print("flip("+str(x)+") = " + str(x))
                print("n^2 = "+str(x**2)+" is flippable")
                break
print(str(int(time.time() - t0)) + " seconds")

 

This is actually slower for small numbers, but eventually it is less work for the computer to manage, and becomes quicker at very large numbers.

Still, It’s not very smart, It iterates through and examines countless multiples of 2011 which could and should be skipped entirely… which

The number 16088002011000000000000 is a multiple of 2011, but flip(16088002011000000000000) doesn’t equal 16088002011000000000000, so property B is false. This is a 23 digit number, and the 11th digit is 1, while it’s flipped position (13th) is the digit 0. this means we will need to change the 11th digit before even having a chance for the number satisfying property B. so, there’s no need to examine as we add 2011 until we change the 11th digit, and since the 11th digit’s unit change is 10^10, we will need to add it (10^10/2011) times before there’s even a chance to satisfy property B.

A number like 40220000000000000000 has no chance of being even flippable until the leading digit changes, which is ~ 5*10^15 additions later…

So this is clearly not a perfect algorithm we have here.

 

The above programs are good enough to find the smallest integer that satisfies the conditions of the puzzle, but even with 24hrs of computation time, similar attempts don’t find the extra credit number which asks for the same conditions except for a remainder of 100 when divided by 2011.

 

Lets do some basic math.

for any integer:

Property A:

well each digit has a 7 in 10 chance of being flippable, and in base 10 an integer has log( n ) digits, so the probability that n is flippable is (7/10)^log(n)

for a 10 digit number, its:

and for each flippable number, the odds that flip(n) = n is, well for each digit it’s 1 in 7 probability that its flipped value is what the mirrored digit spot has.

so basically the odds that the first half of the digits in a number (when flipped) are the corresponding digits on the other side of the number is (1/7)^int(log(n)/2)

probability n is flippable flip(n)=n(assuming n is flippable) both(Property A)
n (7/10)^int(log(n)+1) (1/7)^int((log(n)+1)/2) (7/10)^int(log(n)+1) *(1/7)^int((log(n)+1)/2)
n~=5*10^4 1.7 * 10^-1 2.0 * 10^-2 3.4 * 10^-3
n~=5*10^8 4.0 * 10^-2 4.2 * 10^-4 1.7 * 10^-5
n~=5*10^16 2.3 * 10^-3 1.7 * 10^-7 4.0 * 10^-10
n~=5*10^32 7.7 * 10^-6 3.0 * 10^-14 2.3 * 10^-19

 

Property B: (is n^2 flippable)

well n^2 has int(log(n^2)+1) digits, each one has a 7/10th chance of being flippable, so n^2’s probability of being flippable is (7/10)^int(log(n^2)+1).

probability that n^2 if flippable
n (7/10)^int(log(n^2)+1)
n~=5*10^4 3.9 * 10^-4
n~=5*10^8 4.5 * 10^-7
n~=5*10^16 1.2 * 10^-12
n~=5*10^32 4.1 * 10^-24

 

Property C: (n is divisible by 2011)

any integer n has 1/2011 ~= 5 * 10^-4 probability of being divisible by 2011

approximate probability n is flippable and flip(n)=n n^2 is flippable n is divisible by 2011
n~=5*10^4 3.4 * 10^-3 3.9 * 10^-4 5.0 * 10^-4
n~=5*10^8 1.7 * 10^-5 4.5 * 10^-7 5.0 * 10^-4
n~=5*10^16 4.0 * 10^-10 1.2 * 10^-12 5.0 * 10^-4
n~=5*10^32 2.3 * 10^-19 4.1 * 10^-24 5.0 * 10^-4

 

so by these numbers, its clear that building numbers divisible by 2011 and then checking the other conditions is the a really bad methodology for large numbers, since being divisible by 2011 is incredibly common relative to the other conditions. and building numbers using the rarest condition is best, as it means fewer numbers checked before finding a match on all properties.

It’s therefore tempting to build huge numbers that are flippable, (huge numbers being n^2), then taking the square root and checking property A and then C.  The problem with this of course that most flippable numbers do not have integer square roots, lets look at that bit of probability:

approximate probability that n^2 is flippable an integer around n^2’s magnitude has an integer square root
n (7/10)^int(log(n^2)+1) 1/((n+1)^2 – n^2) = 1/(2n+1)
n~=5*10^4 3.9 * 10^-4 1.0 * 10^-5
n~=5*10^8 4.5 * 10^-7 1.0 * 10^-9
n~=5*10^16 1.2 * 10^-12 1.0 * 10^-17
n~=5*10^32 4.1 * 10^-24 1.0 * 10^-33

 

so you will have to build 2n+1 numbers (approximately) to increment n once.  In other words its rare-er that it’s a perfect square, then flippable.

 

 

 

 

My next attempt was incrementing (although not exactly in order) through flippable integers, and appending each with its own flipped mirror image.  so lets say I have 1230556, I would append to the left 9550321 to create 95503211230556, which is flippable, and who’s flipped value is itself.  This is not immediately easy to do, as the vast majority of numbers, especially as you get large aren’t flippable, ( we computed the probability that n is flippable is about (7/10)^int(log(n)+1) ).  Well being flippable simply means no digit in the decimal representation is 3 or 4 or 7.  So every flippable digit has 7 options instead of 10, that seems a lot like base 7 to me.

So I’m going to increment flippable integers by incrementing a base 7 integer.  each base 7 digit represents one of the filppable base 10 digits, and simply transform it to the flippable decimal with:

0->0, 1->1, 2->2, 3->5, 4->6, 5->8, 6->9 per digit.

Even if python could innately give me the base7 string of an integer, we know from our first couple attempts that converting each and every huge integer we create into a string isn’t entirely wise, as most of the work is repeated for huge numbers.  So I used a list of integers, values ranging from 0 through 7, each index represents a digit’s place, and the integer value at each index is the digit’s value.  Just as we did before with our array code, I have an add/carry-over function to deal with incrementing our base 7 number, this is rarely taxed because the vast majority of increments don’t involve (m)any carryovers.

import time

def incementlistx(listb7):
    idx = 0
    go = True
    listb7[idx]+=1
    while go:
        go=False
        if listb7[idx]==7:
            if idx == 0:
                listb7[idx]=1
            else:
                listb7[idx]=0
            if len(listb7) <= idx+1:
                listb7=[1]
                for x in range(0,idx+1):
                    listb7.append(0)
                break
            listb7[idx+1]+=1
            if listb7[idx+1]==7:
                go=True
                idx+=1
    return listb7

def cdecimal(listb7):
    #generates two integers from listb7, assuming there is a mirrored image (flipped) of listb7 to the left of it.
    #one for even , and one for odd number of digits.
    odd=0
    even=0
    for i in range(0,len(listb7)):
        odd+=o[listb7[i]]*10**i
        if i!=len(listb7)-1:
            odd+=f[listb7[i]]*10**(2*(len(listb7)-1)-i)
        even+=o[listb7[i]]*10**i
        even+=f[listb7[i]]*10**(2*(len(listb7))-1-i)
    return [odd,even]

def isflippable(x):
    for c in str(x):
        if c in ["3","4","7"]:
            return False
    return True

o=[0,1,2,5,6,8,9]
f=[0,1,2,5,9,8,6]
t0 = time.time()
listb7 = [1]
#listb7 is a list of base7 digits that represents the right half of the integer n.
while True:
    listb7=incementlistx(listb7)
    for n in cdecimal(listb7):
        r = n%2011
        if r==100 or r==0:
            if isflippable(n**2):
                print(str(n) + " has a remainder of "+str(r)+" when divided by 2011")
                print(str(int(time.time() - t0)) + " seconds")

 

outputs:

 

5000261920005 has a remainder of 0 when divided by 2011
6 seconds
5001008001005 has a remainder of 0 when divided by 2011
13 seconds
1062212556552122901 has a remainder of 0 when divided by 2011
6112 seconds
106068858858858890901 has a remainder of 0 when divided by 2011
41447 seconds
500555602966209555005 has a remainder of 0 when divided by 2011
47190 seconds
10962025901110652029601 has a remainder of 100 when divided by 2011
140140 seconds

This code finds the first answer in 6 seconds, and our first attempt at the top of the page took 35 minutes to do the same task. (!!!)

It takes a while, but it does find the smallest number satisfying the extra credit conditions.

Note: all of these little programs will probably be around a thousand times faster if written in java or C/C++.

 

So that concludes my time with this puzzle, but if I wanted to make an even better/faster piece of software for a similar task lets look at those probabilities again:

approximate probability n is flippable and flip(n)=n n^2 is flippable n is divisible by 2011
n~=5*10^4 3.4 * 10^-3 3.9 * 10^-4 5.0 * 10^-4
n~=5*10^8 1.7 * 10^-5 4.5 * 10^-7 5.0 * 10^-4
n~=5*10^16 4.0 * 10^-10 1.2 * 10^-12 5.0 * 10^-4
n~=5*10^32 2.3 * 10^-19 4.1 * 10^-24 5.0 * 10^-4
approximate probability that n^2 is flippable an integer around n^2’s magnitude has an integer square root
n (7/10)^int(log(n^2)+1) 1/((n+1)^2 – n^2) = 1/(2n+1)
n~=5*10^4 3.9 * 10^-4 1.0 * 10^-5
n~=5*10^8 4.5 * 10^-7 1.0 * 10^-9
n~=5*10^16 1.2 * 10^-12 1.0 * 10^-17
n~=5*10^32 4.1 * 10^-24 1.0 * 10^-33

All things equal, if there were multiple properties to check, and it was equally as costly to check each, you’d check the rarest first, so you can eliminate the number faster, minimizing the total number of checks.

Clearly the rarest thing for a number n is that it’s square is flippable, so maybe we want to increment through the perfect squares, checking if the number is flippable, then checking if the square root is flippable and if flip of the square root is itself, then checking the remainder when divided by 2011…   but how do you increment through perfect squares? well that’s easy.

for any perfect square n^2, the next perfect square is (n+1)^2, which is n^2+2n+1, so if we know n^2 (the current perfect square), we can add 2n+1 to jump to the next one, checking if its flippable at each jump.

Let me know if you think this would indeed be better or not, why?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: