Happy tickets up to 300 digits

It all started with a test job for the job “js-developer, Node.js-developer”, and then I was besieged: the task for happy tickets.

Count the number of lucky tickets for 2, 4, 6, 8 and 10 digital values.

I am sure that many people have done this banal task several times, but, as a rule, for 6 digits ( for those who do not understand what will be discussed ).

Banal solution:

var sum = function(num){ //      var str = num.toString(), arr = str.split(''), s = 0; arr.forEach(function(value){ s+=parseInt(value); }); return s; }, luckyTickets = function(len){ var lenMiddle = len/2, maxSize = Math.pow(10,lenMiddle), result = 0; for(var i=0;i<maxSize;i++) for(j=0;j<maxSize;j++) if( sum(i) == sum(j) ) result++; return result; }; console.log( luckyTickets(8) ); // 4 816 030 

You can also see here .
')
And if the number 10? thirty? 200? Trouble I had to wait long for the result: the analog in PHP (5.3) was “dying”, even when I gave 10 numbers and set_time_limit (3600).

Now back to the world of JS. Despite the fact that simple loops in Node.js are executed faster than in PHP, the execution time still does not suit me (1 029 458 ms).

And now enough of this dull text, go to an alternative solution.

The clue itself turned out to be in Kvant magazine, No. 12 (1976), pp.68–70 ( electronic version ).

There you can also see the output - a table with which you can easily find out the “amount of happiness” in tickets of 2 (n = 1), 4 (n = 2), 6 (n = 3) and 8 (n = 4) numbers.

How to fill the table is shown below:



That is, the sum of 10 elements of the previous column, for which the index is <= the desired value. The number of lucky tickets is equal to the sum of each value squared in a specific column:

- for n = 1 (2 digits) -> 1 ^ 2 + 1 ^ 2 + ... + 1 ^ 2 = 10;
- for n = 2 (4 digits) -> 1 ^ 2 + 2 ^ 2 + ... + 1 ^ 2 = 670;
- for n = 3 (6 digits) -> 1 ^ 2 + 3 ^ 2 + ... + 75 ^ 2 + ... + 1 ^ 2 = 55 252;
- for n = 4 (8 digits) -> 1 ^ 2 + 3 ^ 2 + ... + 670 ^ 2 + ... + 1 ^ 2 = 4 816 030;

Further our turn.

 var getNextArr = function(prevArr){ //        var newLen = prevArr.length + 9, //       9 arr = []; //   for(var i=0; i<newLen; i++){ var q = 0; //    for(j=0; j<10; j++) //  10   if(prevArr[ij]) // ...      q+=prevArr[ij]; //  arr[i] = q; //  arr.push(q); } return arr; }, luckyTickets = function(num){ //    var arr = [], //   result = 0; // ,    for(i=0;i<10;i++) arr.push(1); //     10  for(i=0;i<(num/2-1);i++) //    arr = getNextArr(arr); //    arr.forEach(function(v){ result+=Math.pow(v,2); }); //       return result; }; 

Well, you need to check:

 console.log( luckyTickets(300) ); // 8.014950093120178e+297 ** 

Actually, what it was all about: a runtime of 106 ms (!!!), it’s scary to imagine what would happen when using the banal method.

* all javascript checked on Node.js (x32)
** maximum length of ticket number - 310, more? - the result goes to the Infinity area.
*** This is my first article on Habré for the last 3 years, please do not throw stones.