This paper deals with codebooks assigning to each word or phrase in a (long) list a 5-digit ‘group’ which is a multiple of three or scannable in the jargon of WW2. Here the groups are allowed to have initial 0s: thus 12345 and 00078 are groups.
Being a multiple of three (equivalently, being divisible by three) means that the corresponding number, 12345 or 78 in these examples, is a multiple by three or, equivalently, the sum of the five digits, 15 in both examples, is a multiple of three.
The characteristic χ of such a group is defined to be the reduction modulo 10 of the sum of the five digits: thus χ(12345) = 5.
One might well guess that of the 33334 scannable groups from 00000 to 99999 about 3333 have characteristic 0, about another 3333 have characteristic 1, etc. This is far from being the case. A simple electronic calculation checks that for 0 ≤ i ≤ 9 the number m(i) of scannable groups with characteristic i is as set out below:
m(0) = 3247 m(1) = 5875 m(2) = 1780 m(3) = 1780 m(4) = 5875
m(5) = 3247 m(6) = 925 m(7) = 4840 m(8) = 4840 m(9) = 925.
These Mamba numbers, were known to the American naval cryptanalysis unit Op-20-G in 1943 but the calculation must have been quite tedious. Working out that it was worth calculating at all was a major achievement in cryptanalysis.
Понятно, что для 5-значных групп прямой перебор решит задачку в момент.
Требуется написать прогу, которая будет вычислять mamba numbers для произвольного n. Ну чтобы не создавать проблем любителям С и Java пусть n ≤ 18. Этого достаточно уже, чтобы тут уже не работал брютфорс.