获取模10序列的第n个元素

Question

我尝试解决以下比赛：

考虑使用以下算法生成无限序列a的十进制数字：

• 最初给出前五个数字；
• 对于i > 4, a[i] = (a[i - 5] + a[i - 4] + a[i - 3] + a[i - 2] + a[i - 1]) % 10，即从第五个元素开始，每个元素都是前五个元素模10的和。

我需要找到序列的第n个元素（第一个元素的索引为0）。

我的尝试如下：

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

对于小的n值，它可以工作，但当测试有大数（如521687676）时就无法正常工作。

我是否漏掉了什么？我猜可以推导出一个公式而不是使用循环。

- Mihai Alexandru-Ionut

---

如果你发现有5个条目与之前的5个条目相匹配，那么从那时开始模式将重复出现... 例如，如果你有123456123456123456....，那么在位置6,000处的数字将是1。 - Jonas Wilms

前五个数字是什么？ - nice_dev

@vivek_23，[1,2,3,4,5] - Mihai Alexandru-Ionut

@MihaiAlexandru-Ionut 看起来 [OEIS]（http://oeis.org/search?q=1%2C2%2C3%2C4%2C5%2C5%2C9%2C6%2C9%2C4%2C3%2C1%2C3%2C0%2C1%2C8%2C3%2C5%2C7%2C4%2C7%2C6%2C9%2C3%2C9%2C4%2C1%2C6%2C3%2C3%2C7%2C0%2C9%2C2%2C1%2C9%2C1%2C2%2C5%2C8%2C5%2C1%2C1%2C0%2C5%2C2%2C9%2C7%2C3%2C6%2C7%2C2%2C5%2C3%2C3%2C0%2C3%2C4%2C3%2C3%2C3%2C6%2C9%2C4%2C5%2C7%2C1%2C6%2C3%2C2%2C9%2C1%2C1%2C6%2C9%2C6%2C3%2C5%2C9%2C2%2C5%2C4%2C5%2C5%2C1%2C0%2C5%2C6%2C7%2C9%2C7%2C4%2C3%2C0%2C3%2C7%2C7%2C0%2C7%2C4%2C5&language=english&go=Search) 没有给出任何线索。在模式中找到循环是棘手的，而且并不显然。 - nice_dev

Answer 1

只有 100,000 种可能的五位数字序列，所以在某个时候，任何输入都会开始重复。使用哈希来查找您的输入序列何时开始重复。计算循环长度。减去最大可能的完整循环并继续进行余数。

运行时间为 O(10^r)，其中 r 是序列长度。对于较大的 r 来说这很糟糕，但对于 r=5 来说则可以接受。

- Dave

Answer 2

这里是实现代码，就像@Dave建议的那样。观察后，我认为对于给定的任何五个数字来说，循环长度都是固定的，即% 10为4686。

如果您没有得到正确的答案，请检查我是否犯了任何愚蠢的错误。

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

- shubhambharti201

Answer 3

正如@shubhambharti201所指出的，无论您从哪里开始，都会得到一个重复每4686个数字的循环，这将使问题简化为数万次操作，无论N有多大。

但我们可以做得更好。

首先，请注意我们可以通过中国剩余定理从x%5和x%2计算x%10：https://en.wikipedia.org/wiki/Chinese_remainder_theorem 如果我们使用较小的模数，我们就会得到较短的循环。使用5作为模数，数字周期的长度为781.使用2则只有长度为6。这些长度的最小公倍数是781*6=4686，正如我们所期望的那样。

此外，这是一种线性操作，这意味着我们可以将以X开头的序列加到以Y开头的序列上，以得到以X+Y开头的序列。如果我们知道从“10000”开始的序列，则非常容易计算我们需要的所有序列。对于模数2和5开始的周期足够小，我们可以把它们写到程序中，然后使用它们来回答任何此类问题，只需进行少量操作即可：

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

- Matt Timmermans

---

优化得很棒 :) - Kamil Kiełczewski

Answer 4

你创建了一个大数组来处理大的n值 - 这可能是你的代码在每次运行后产生不同（随机）结果并有时会导致Chrome浏览器崩溃的原因（我在控制台中运行它）。尝试使用以下方法（仅使用5个元素的数组）。

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]) );

- Kamil Kiełczewski