I tried to solve the following contest:

Consider an infinite sequence a of decimal digits which is generated using the following algorithm:

• the first 5 digits are initially given;
• for i > 4, a[i] = (a[i - 5] + a[i - 4] + a[i - 3] + a[i - 2] + a[i - 1]) % 10, i.e. each element starting with the fifth is the sum of the previous five elements modulo 10.

I need to find the nth element of the sequence (the first element has index 0).

What I tried is:

while(a.length <= n){
    var sum = a.slice(-5).reduce((a, b) => a+b, 0);
    a.push(sum % 10);
}
return a.pop()

For small n values it works but it's not working when the tests have large numbers(like 521687676).

Is anything I missed it ? I guess that it can be deduced a formula instead of loops.

I tried to solve the following contest:

Consider an infinite sequence a of decimal digits which is generated using the following algorithm:

• the first 5 digits are initially given;
• for i > 4, a[i] = (a[i - 5] + a[i - 4] + a[i - 3] + a[i - 2] + a[i - 1]) % 10, i.e. each element starting with the fifth is the sum of the previous five elements modulo 10.

I need to find the nth element of the sequence (the first element has index 0).

What I tried is:

while(a.length <= n){
    var sum = a.slice(-5).reduce((a, b) => a+b, 0);
    a.push(sum % 10);
}
return a.pop()

For small n values it works but it's not working when the tests have large numbers(like 521687676).

Is anything I missed it ? I guess that it can be deduced a formula instead of loops.

• javascript
• algorithm

• 5 If you find 5 entries that match 5 previous entries, the pattern will repeat from then on ... e.g. if you have 123456123456123456.... then the digit at position 6.000 will be 1. – Jonas Wilms Commented Nov 28, 2019 at 10:30
• What are the first five numbers though? – nice_dev Commented Nov 28, 2019 at 10:51
• @vivek_23, [1,2,3,4,5] – Mihai Alexandru-Ionut Commented Nov 28, 2019 at 10:52
• @MihaiAlexandru-Ionut Apparently, OEIS doesn't give any clue. Finding the cycle in the pattern is tricky and doesn't seem obvious on the eye. – nice_dev Commented Nov 28, 2019 at 11:48

4 Answers 4

There are only 100,000 possible 5 digit sequences, so at some point any input will start repeating. Use a hash to find out when your input sequence has started repeating. Calculate the cycle length. Subtract the max possible full cycles and continue with the remainder.

Running time is O(10^r) where r is the sequence length. This is bad for large r but fine for r=5

As @shubhambharti201 noticed, no matter what you start with, you get a cycle that repeats every 4686 digits, and that reduces the problem to 10s of thousands of operations no matter how big N is.

But we can do way better.

First, note that we can calculate x%10 from x%5 and x%2 by the Chinese Remainder Theorem: https://en.wikipedia/wiki/Chinese_remainder_theorem

If we use a smaller modulus, we get shorter cycles. Using 5 as the modulus, the digit cycle has length 781. Using 2 it has length just 6. The lowest mon multiple of these lengths is 781*6 = 4686 as we would expect.

Futhermore, this is a linear operation, meaning that we can add the sequence that starts with X to the sequence that starts with Y to get the sequence that starts wit X+Y. If we know the sequence that starts with "10000", then, it's very easy to pute all the sequences we need. The cycles starting with "10000" for moduli 2 and 5 are small enough that we can just write them into the program, and then use them to answer any such question with only a few operations:

var TWOCYCLE = "100001";
var FIVECYCLE = "10000112431110142300441431323211414111301111430423212033422402034434332020210"
    + "0310431424404413244421013223114102301122123034221213411040111200423431340142131134211144"
    + "11113230421024411220111031111211111042304322120222343410202043434321332104022313103302314"
    + "00330124024220032224334101401123242340322131410404424432032022403103240433443214440301324"
    + "004032432403210121043030014331232142210441043204321001411242042203134121144223013414302044"
    + "003132433022021222411034423144414201301004004313120233031021211223423414414420113224233413"
    + "402040122443034440020131224211032230022212410303231433404402001310004043120014224301032123"
    + "141102323003340002131241142204203432240141012323110221112223041033130021143104202313434040"
    + "144324201413430114400420124412344422132034210020300031431211330304024001220004";

//Get the Nth digit of sequence staring with 10000
function baseDigit(n) {
  var modtwo = TWOCYCLE.charCodeAt(n % TWOCYCLE.length)-48;  //subtract char code for '0'
  var modfive = FIVECYCLE.charCodeAt(n % FIVECYCLE.length)-48;  //subtract char code for '0'
  var modten =  modfive + 5*((modfive+modtwo)%2); //Chinese Remainder theorem
  return modten;
}

function nthDigit(n, start) {
  if (n<5) {
    return start[n]%10;
  }
  var sum=0;
  var basis=start.slice(0);
  // the mod 10 repeating sequence for 10000 ends 0009, so when we add the cycle for digit i, it will
  // add d*9 to the preceding digit i-1.  Add d*1 to the preceeding digit to correct this
  // Start at the end so we include the corrections in the preceding corrections
  for (var i=3;i>=0;--i) {
    basis[i]+=basis[i+1]%10;
  }
  for (var i=0;i<5;i++) {
    sum+=(basis[i]%10)*baseDigit(n-i);
  }
  return sum%10;
}

// Test
var b = [7, 4, 3, 1, 5];
var nth = 521687676;
for (var i=0;i<12;++i)
  console.log(nthDigit(nth+i, b));

Here is the Implementation, what @Dave has suggested. On observation, I think, the cycle length is fixed for any given 5 number with % 10 i.e. 4686.

If you don't get correct answer, check for any silly mistake if I have done.

function getCycleLength(a){
    	var cycleLength, tn;
    	for(let i=0; i<=100000; i++){
    		// starting with t6 i.e. 6th term
    		tn = (a[i+1]+a[i+2]+a[i+3]+a[i+4]+a[i+5]) % 10;
    		a.push(tn);
    		// sequence matching
    		if(a[i+2]==a[1] && a[i+3]==a[2] && a[i+4]==a[3] && a[i+5]==a[4] && a[i+6]==a[5]){
    			console.log("cycle found");
    			cycleLength = i + 1;
    			break;
    		}
    	}
    	return cycleLength;
    }
    
    // To find Nth term. Given first 5 terms in b[]
    function findNth(n, b){
    	var a = [];
    	// To make 1 based-indexing
    	a.push(-1);
    	for(let i=0; i<5; i++){
    		a.push(b[i] % 10);
    	}
    	var cycleLength = getCycleLength(a);
    	console.log(cycleLength);
    	return a[n - Math.floor((n/cycleLength))*cycleLength];
    }
    
    // Sample
    var b = [17, 14, 33, 41, 75];
    var nth = 521687676;
    console.log(findNth(nth, b));

You create large array for large n - this is probably the reason (some kind of 'overflow') why you code produce different (random) results after each run and sometimes broke chrome browser (I run it in console). Try this approach (only 5 element array is used)

function calc(n, a) {
  let i = 4;
  let s=0;
  
  while (i++ < n) {    
    s = (a[0] + a[1] + a[2] + a[3] + a[4]) % 10
    a.shift(); // shift array to left (and remove first item)
    a.push(s); // push s as last (5th) item
  }
  
  return s;
}


// TEST

// Wait ~10 seconds
console.log( calc(521687676,[1, 2, 3, 4, 5]) );