Pandigit checking in Fibonacci Numbers

Project Euler problem 104 is to write an algorithm to determine the first Fibonacci number for which the first 9 digits are 1-9 pandigital and the last 9 digits are also pandigital, where pandigital means that these digits are a permutation of 1 to 9.

Because the answer is going to be a very large number the BigInt class is the most convenient representation for storing and manipulating these numbers. Although the compute time and the amount of storage required will be dominated by the operations of adding, storing and converting these numbers to strings of digits, it is still worthwhile being careful how we create and store the Fibonacci numbers.

Generating the Fibonacci numbers

An obvious approach to generating the numbers in the Fibonacci sequence is to store the numbers in a vector, generating the i’th value from the previous two values and pushing it onto the end of the vector. On a modern computer this approach will be fine for a few hundred or a few thousand values but it will slow down terribly when requiring hundreds of thousands of Fibonacci numbers, as this problem does.

Consider instead storing the last two values in the sequence and updating them. The current state, stored as a vector of two BigInts, is initialized to a pair of ones and thereafter each step involves replacing the second last number by the sum of these two.

One way to do this is to shift the two values on every update, as in

In [1]:
function nextfib(st::Vector{BigInt})
    n = st[1] + st[2]
    st[1] = st[2]
    st[2] = n
    n
end
Out[1]:
nextfib (generic function with 1 method)

However, we may want to store the index into the sequence along with the value, in which case we could represent the state as a user-defined type.

In [2]:
type FibState
    i::Int
    s::Vector{BigInt}
    FibState() = new(2,ones(BigInt,2))    
end

The function FibState defined within the FibState type is an internal constructor. It is used to initialize the state to the second index with both the first and second values being 1, represented as a BigInt.

When we increment a FibState object we can alternate between replacing the first and the second values in the vector s, according to the value of i. We also provide extractors for the value and the index.

In [3]:
function increment(st::FibState)
    s = st.s
    st.i += 1
    s[isodd(st.i) ? 1 : 2] = s[1] + s[2]
    st
end
index(st::FibState) = st.i
value(st::FibState) = st.s[isodd(st.i) ? 1 : 2]
Out[3]:
value (generic function with 1 method)

Let’s check that this works as intended.

In [4]:
st = FibState()
while index(increment(st)) <= 20
    println(index(st),": ",value(st))
end

3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
11: 89
12: 144
13: 233
14: 377
15: 610
16: 987
17: 1597
18: 2584
19: 4181
20: 6765

We are very close to having an iterator which is a type that provides methods for length, start, next and done but we will leave that for another time

Checking for first or last 9 digits being pandigital

Methods for the string function produce character strings from other types of objects. We can add a string method for the FibState type.

In [5]:
import Base.string     # so we can add string methods
string(st::FibState) = string(value(st))
string(st)             # recall that index is now 21
Out[5]:
"10946"

The string itself consists of an vector of bytes (the type Uint8).

In [6]:
names("10946")
Out[6]:
1-element Array{Any,1}:
 :data
In [7]:
typeof("10946".data)
Out[7]:
Array{Uint8,1}

We could use the int function to convert the digits in a string to integers but it is a bit cleaner to subtract the character representation of 0 from the elements.

In [8]:
show("10946".data - '0')

[0x01,0x00,0x09,0x04,0x06]

Next we need to determine if a vector of 9 unsigned integers constitutes a permutation. The isperm function could be used to do this but if we are going to do so hundreds of thousands of times we may wish to be more concise.

We’ll show the function then discuss it.

In [9]:
function isdigitperm(A::Vector{Uint8})
    (length(A) == 9) || return false
    used = falses(9)
    for a in A
        d = a - '0'
        (0 < d < 10) && (used[d] $= true) || return false
    end
    true
end
Out[9]:
isdigitperm (generic function with 1 method)

This special-purpose function checks a vector of bytes to determine if its length is exactly 9 and every byte is in the range ‘1’ to ‘9’ and no value in the range ‘1’ to ‘9’ occurs more than once. The expression

used[d] $= true

replaces used[d] by the exclusive or of used[d] and true. In other words, it negates the logical value and stores the result back into the location at the same time. The first time a digit is flagged as used, the expression returns true. The second time a digit is used it returns false.

Checking for the first or last 9 digits being pandigital or both

In [10]:
function first9pandigital()
    st = FibState()
    while length(string(increment(st))) < 9 end
    while !isdigitperm(string(st).data[1:9])
        increment(st)
    end
    st
end
Out[10]:
first9pandigital (generic function with 1 method)
In [11]:
first9pandigital()
Out[11]:
FibState(2749,[14372689553387917661829645671564334144347634506448917723663290089702222530009397342095721197748390703442578832440606734797476053095767644629443572915711792647722348302386453121454440843797863921561581124399573134833792671117667661197245544556688422949193607193895988306702702760603047336208386100938317422813175407356709232675779685357629997245797294804250463809150187026942349354902182628605422407739419382801150894021953277500195893045355811369520046888338772777218694864406890501694863448727599353830662539700881454734823358742184362414868465995609763288002569665002250249,8882810653744279514485694748125812375732849751297108255084959486990434372916634744577818914260701869600909783888810024985796146896310939747463302125919319171019482090197974901998607036334499473051061534789819562244913549076712416681135135769854879654325478116593469709577420996729583173003248763591736108420837371980297490974395916653387025703790294927230273060942921777620545005278746683898207840517062790672861160964463309578409134888733561142463260314071777151855683804048280701113956693827906336793011366003791501139124180416150996570324585861472852993251848309768327376])
In [11]:
@time first9pandigital();

elapsed time: 0.015653844 seconds (6323525 bytes allocated)

Notice that we time the second execution of the function. The first execution can be much slower than subsequent executions because the function is compiled the first time it is called with an argument signature. (In the the case of first9pandigital there is only one method definition and that is for an empty argument list.)

Instead of showing these potentially very large numbers, we create a show method for the FibState type that prints an abbreviated version.

In [12]:
import Base.show   # so we can add show methods
function show(io::IO, st::FibState)
    s = string(st)
    println(io, "Fib[", st.i,"] = ",s[1:10],"...",s[end-9:end],
            ", ", length(s), " decimal digits")
end
show(first9pandigital())

Fib[2749] = 1437268955...5002250249, 575 decimal digits
In [13]:
function last9pandigital()
    st = FibState()
    while length(string(increment(st))) < 9 end
    while !isdigitperm(string(st).data[end-8:end])
        increment(st)
    end
    st
end
show(last9pandigital())

Fib[541] = 5162123292...8839725641, 113 decimal digits
In [13]:
@time last9pandigital();

elapsed time: 0.001514266 seconds (375743 bytes allocated)

Finally, create a function that allows for checking either the first 9 digits or the last 9 digits or both.

In [14]:
function fibpandigit(first::Bool,last::Bool)
    st = FibState(); while length(string(increment(st))) < 9 end
    while !((!first || isdigitperm(string(st).data[1:9])) &&
            (!last || isdigitperm(string(st).data[end-8:end])))
         increment(st)
    end
    st
end
show(fibpandigit(true,false))  # should be same as first9pandigital

Fib[2749] = 1437268955...5002250249, 575 decimal digits
In [15]:
show(fibpandigit(false,true))

Fib[541] = 5162123292...8839725641, 113 decimal digits
In [15]:
@time res = fibpandigit(true,true);

elapsed time: 558.664758252 seconds (60210195439 bytes allocated)
In [16]:
show(res)

Fib[329468] = 2456817391...0352786941, 68855 decimal digits

Project Euler problem 104 is to write an algorithm to determine the first Fibonacci number for which the first 9 digits are 1-9 pandigital and the last 9 digits are also pandigital, where pandigital means that these digits are a permutation of 1 to 9.

Because the answer is going to be a very large number the BigInt class is the most convenient representation for storing and manipulating these numbers. Although the compute time and the amount of storage required will be dominated by the operations of adding, storing and converting these numbers to strings of digits, it is still worthwhile being careful how we create and store the Fibonacci numbers.

Generating the Fibonacci numbers

An obvious approach to generating the numbers in the Fibonacci sequence is to store the numbers in a vector, generating the i’th value from the previous two values and pushing it onto the end of the vector. On a modern computer this approach will be fine for a few hundred or a few thousand values but it will slow down terribly when requiring hundreds of thousands of Fibonacci numbers, as this problem does.

Consider instead storing the last two values in the sequence and updating them. The current state, stored as a vector of two BigInts, is initialized to a pair of ones and thereafter each step involves replacing the second last number by the sum of these two.

One way to do this is to shift the two values on every update, as in

In [1]:
function nextfib(st::Vector{BigInt})
    n = st[1] + st[2]
    st[1] = st[2]
    st[2] = n
    n
end
Out[1]:
nextfib (generic function with 1 method)

However, we may want to store the index into the sequence along with the value, in which case we could represent the state as a user-defined type.

In [2]:
type FibState
    i::Int
    s::Vector{BigInt}
    FibState() = new(2,ones(BigInt,2))    
end

The function FibState defined within the FibState type is an internal constructor. It is used to initialize the state to the second index with both the first and second values being 1, represented as a BigInt.

When we increment a FibState object we can alternate between replacing the first and the second values in the vector s, according to the value of i. We also provide extractors for the value and the index.

In [3]:
function increment(st::FibState)
    s = st.s
    st.i += 1
    s[isodd(st.i) ? 1 : 2] = s[1] + s[2]
    st
end
index(st::FibState) = st.i
value(st::FibState) = st.s[isodd(st.i) ? 1 : 2]
Out[3]:
value (generic function with 1 method)

Let’s check that this works as intended.

In [4]:
st = FibState()
while index(increment(st)) <= 20
    println(index(st),": ",value(st))
end

3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
10: 55
11: 89
12: 144
13: 233
14: 377
15: 610
16: 987
17: 1597
18: 2584
19: 4181
20: 6765

We are very close to having an iterator which is a type that provides methods for length, start, next and done but we will leave that for another time

Checking for first or last 9 digits being pandigital

Methods for the string function produce character strings from other types of objects. We can add a string method for the FibState type.

In [5]:
import Base.string     # so we can add string methods
string(st::FibState) = string(value(st))
string(st)             # recall that index is now 21
Out[5]:
"10946"

The string itself consists of an vector of bytes (the type Uint8).

In [6]:
names("10946")
Out[6]:
1-element Array{Any,1}:
 :data
In [7]:
typeof("10946".data)
Out[7]:
Array{Uint8,1}

We could use the int function to convert the digits in a string to integers but it is a bit cleaner to subtract the character representation of 0 from the elements.

In [8]:
show("10946".data - '0')

[0x01,0x00,0x09,0x04,0x06]

Next we need to determine if a vector of 9 unsigned integers constitutes a permutation. The isperm function could be used to do this but if we are going to do so hundreds of thousands of times we may wish to be more concise.

We’ll show the function then discuss it.

In [9]:
function isdigitperm(A::Vector{Uint8})
    (length(A) == 9) || return false
    used = falses(9)
    for a in A
        d = a - '0'
        (0 < d < 10) && (used[d] $= true) || return false
    end
    true
end
Out[9]:
isdigitperm (generic function with 1 method)

This special-purpose function checks a vector of bytes to determine if its length is exactly 9 and every byte is in the range ‘1’ to ‘9’ and no value in the range ‘1’ to ‘9’ occurs more than once. The expression

used[d] $= true

replaces used[d] by the exclusive or of used[d] and true. In other words, it negates the logical value and stores the result back into the location at the same time. The first time a digit is flagged as used, the expression returns true. The second time a digit is used it returns false.

Checking for the first or last 9 digits being pandigital or both

In [10]:
function first9pandigital()
    st = FibState()
    while length(string(increment(st))) < 9 end
    while !isdigitperm(string(st).data[1:9])
        increment(st)
    end
    st
end
Out[10]:
first9pandigital (generic function with 1 method)
In [11]:
first9pandigital()
Out[11]:
FibState(2749,[14372689553387917661829645671564334144347634506448917723663290089702222530009397342095721197748390703442578832440606734797476053095767644629443572915711792647722348302386453121454440843797863921561581124399573134833792671117667661197245544556688422949193607193895988306702702760603047336208386100938317422813175407356709232675779685357629997245797294804250463809150187026942349354902182628605422407739419382801150894021953277500195893045355811369520046888338772777218694864406890501694863448727599353830662539700881454734823358742184362414868465995609763288002569665002250249,8882810653744279514485694748125812375732849751297108255084959486990434372916634744577818914260701869600909783888810024985796146896310939747463302125919319171019482090197974901998607036334499473051061534789819562244913549076712416681135135769854879654325478116593469709577420996729583173003248763591736108420837371980297490974395916653387025703790294927230273060942921777620545005278746683898207840517062790672861160964463309578409134888733561142463260314071777151855683804048280701113956693827906336793011366003791501139124180416150996570324585861472852993251848309768327376])
In [11]:
@time first9pandigital();

elapsed time: 0.015653844 seconds (6323525 bytes allocated)

Notice that we time the second execution of the function. The first execution can be much slower than subsequent executions because the function is compiled the first time it is called with an argument signature. (In the the case of first9pandigital there is only one method definition and that is for an empty argument list.)

Instead of showing these potentially very large numbers, we create a show method for the FibState type that prints an abbreviated version.

In [12]:
import Base.show   # so we can add show methods
function show(io::IO, st::FibState)
    s = string(st)
    println(io, "Fib[", st.i,"] = ",s[1:10],"...",s[end-9:end],
            ", ", length(s), " decimal digits")
end
show(first9pandigital())

Fib[2749] = 1437268955...5002250249, 575 decimal digits
In [13]:
function last9pandigital()
    st = FibState()
    while length(string(increment(st))) < 9 end
    while !isdigitperm(string(st).data[end-8:end])
        increment(st)
    end
    st
end
show(last9pandigital())

Fib[541] = 5162123292...8839725641, 113 decimal digits
In [13]:
@time last9pandigital();

elapsed time: 0.001514266 seconds (375743 bytes allocated)

Finally, create a function that allows for checking either the first 9 digits or the last 9 digits or both.

In [14]:
function fibpandigit(first::Bool,last::Bool)
    st = FibState(); while length(string(increment(st))) < 9 end
    while !((!first || isdigitperm(string(st).data[1:9])) &&
            (!last || isdigitperm(string(st).data[end-8:end])))
         increment(st)
    end
    st
end
show(fibpandigit(true,false))  # should be same as first9pandigital

Fib[2749] = 1437268955...5002250249, 575 decimal digits
In [15]:
show(fibpandigit(false,true))

Fib[541] = 5162123292...8839725641, 113 decimal digits
In [15]:
@time res = fibpandigit(true,true);

elapsed time: 558.664758252 seconds (60210195439 bytes allocated)
In [16]:
show(res)

Fib[329468] = 2456817391...0352786941, 68855 decimal digits

source

Similar Notebooks

 

 

Leave a comment

Your email address will not be published. Required fields are marked *