Goal

The goal of this competition is to create a clever and fast algorithm that achieves the set result. The algorithm must be implemented on an Arduino Nano Every, which will be provided free of charge by Dekimo after registration. You can also keep the Arduino after the competition.

The winner is the one who has a correctly working algorithm and that is the fastest on different test vectors chosen by Dekimo. The record scoreboard will be kept on this page. Every time someone beats the existing record, that person will receive a nice prize and, if approved, their name will be listed as the new record holder on our website.

Description of task

The technical details of the assignment are further explained in the document that will be received after registration.

The operation “factorial” in mathematics probably does not need an introduction. The factorial of a number n is denoted by n! and is the product of all integers from 1 to n (incuding n). Thus, 5! = 1x2x3x4x5 = 120. In combinatorics, this is the number of permutations of 5 elements, or thus the number of possible anagrams of words of 5 letters. In a basic programming course, the factorial is often used to introduce recursion, since n! = n . (n-1)!. Too little is said about the fact that this kind of tail recursion is unnecessarily greedy and inefficient and is better replaced by an iterative loop, but that’s beside the point.

Anyone who has ever calculated factorials knows that the results become very large very quickly. The factorial grows faster than the exponential function. In a manual calculation, the fun stops after the first ten factorials. Microsoft Excel already gives up at 21! because the result no longer fits in a 64-bit data type. Many calculators give up at 70!, a number that is more than one hundred digits long. The built-in Google calculator stops at 171!, a number of over three hundred digits that no longer fits in a 1024-bit datatype.

We are going to start with the Arduino where Google gives up and where Microsoft has long disappeared from the rear view mirror. We are not going to calculate large factorials, as this would be boring and uninspiring. We are going to keep it fun. The Arduino will receive a number string that is already a factorial. In that number string, two consecutive digits will be masked. These digits will have been replaced by ‘xy’. An algorithm needs to be implemented on the Arduino that will calculate the two missing digits x and y.

Let’s take something small and manageable as an example, the factorial of 21, 21!= 51090942171709440000. The Arduino receives as input 510909xy171709440000 and must deduce that this can only be a factorial if xy=42. Clearly, for large numbers such as 999! the method that first calculates the factorial in full is not the ideal solution, or even impossible with the limited resources on the embedded microcontroller.

At first glance, this task may seem impossible. After all, there is no fixed pattern in the numbers of factorials. Yet, with some ingenuity, it is possible to find connections between x and y that allow the solution to be determined unambiguously, without actually having to calculate the factorial.