By 40 it's over 10^(100000)

Computer Science Level 3

A sequence of positive integers $S$ with $S_1=S_2=1$ is further defined by $S_k=S_{k-1}\times S_{k-2}+1$ for $k > 2.$

The second time in the sequence that the last three digits of $S_{n}$ will equal the last three digits of $S_{n+1}$ will occur at $S_{n=A},$ whose last three digits are $B.$ Find $A+B.$

$\textbf{Details and Assumptions}$
The first time is the trivial case at $S_{n=1}.$
For example, if the last three digits of both $S_{193}$ and $S_{194}$ were both $329,$ then $A=193$ and $B=329$ so the answer would be $522.$

The answer is 1172.

4 solutions

Vineeth Chelur
Apr 27, 2014

Used a simple code to solve it

public class Main

{

public static void main(String[] args)
{
    long a,b,c;
    a=1;
    b=1;
    for(int n=2;;n++)
    {
        c=a*b+1;
        a=b%1000;
        b=c%1000;
        if(a%1000==b%1000)
        {
            System.out.println(a%1000+n);
            break;
        }
    }
}

}

why is it a=b%1000; b=c%1000, instead of a =b; b=c;

Rahul Badenkal - 6 years, 10 months ago

Sorry for the really late reply. If we do a=b and b=c, we end up with really large numbers. To avoid that, it's sufficient to take mod(1000),i.e. last 3 digits.

Vineeth Chelur - 6 years, 4 months ago

Franklyn Wang
Jul 11, 2014

In python:

def recur(n):
    recurlist = [1, 1]
    for r in range(2, n+1):
        k = (recurlist[r-1]*recurlist[r-2]+1)%1000
        recurlist.append(k)
    return recurlist[-2]

for r in range(2, 999):
    if recur(r)==recur(r+1):
        print(r)
        print(recur(r))
        break

Thaddeus Abiy
Apr 29, 2014

Because the sequence grows very fast,we will save a lot of time and memory by just keeping track of the last three digits.Thus we do all operations $mod (1000)$ .

Code in python:

a , b , n  = 1 , 1 , 3
while True:
    c = (a * b + 1) % 1000
    if c == b:
        print (n-1)+b
        break
    a , b , n = b , c , n + 1

Kenny Lau
Aug 29, 2014

Java code:

public class brilliant{
    public static void main(String args[]){
        int n=1;
        int prev=1,cur=1,next;
        while(true){
            next = (prev*cur+1)%1000;
            prev = cur;
            cur = next;
            n++;
            if(prev==cur) break;
        }
        System.out.println(n+prev);
    }
}

By 40 it's over 10^(100000)

The answer is 1172.

4 solutions

{

0 pending reports