## Teaser 2945: Infernal indices

**From The Sunday Times, 3rd March 2019** [link]

The above is the size of the evil multitude in the last “Infernal indices” novel: “A deficit of daemons”.

Spoiler Alert:At the end, the forces of good engage in the fewest simultaneous battles that prevent this evil horde splitting, wholly, into equal-sized armies for that number of battles. The entire evil horde is split into one army per battle, all equally populated, bar one which has a deficit of daemons, leading to discord and a telling advantage for the forces of good.How many battles were there?

[teaser2945]

## Jim Randell 8:15 am

on25 February 2019 Permalink |Although the given number (let’s call it

N) is large (it is 36,306 decimal digits), it is not too large forPythonto cope with.We need to find the smallest whole number

nthatdoes notdivideN. This is a much smaller number.The following Python program runs in 107ms.

Run:[ @repl.it ]Solution:There were 17 battles.(N mod 17) = 14, so the best the evil horde could manage would be 16 armies the same size and 1 army that had 3 fewer demons.LikeLike

## Jim Randell 4:46 pm

on2 March 2019 Permalink |We can use the technique given in

Enigma 1494to compute the residues of large powers without the need to construct the huge numbers.The internal runtime for the following program is significantly less than the simple program given above (169µs vs. 961µs for the program given above). Although in practise both programs run instantaneously.

Using the 3-argument version of the Python builtin [[

`pow()`

]] instead of [[`mpow()`

]] gets the internal run time down to 40µs.For a manual solution we can use “the difference of two squares” method to express the number as:

From which it is easy to see that

Nwill have a large number of factors of 2 and 3, and the fact that any power of 6 ends in a 6 means that the difference of two powers of 6 will end in a 0, so it will also be divisible by 5.So we can start by considering the primes: 7, 11, 13, 17, 19, 23 when looking for a suitable

n.When evaluating

mpow(6, x, n)the exponent can be reduced modulo(n – 1)(asnis prime) usingEuler’s Theorem, and we can always evaluate thempow(x, 6, n)in 3 iterations.In the end we don’t even need to consider all these primes in order to get the answer, so we can arrive at the solution with only a modest amount of calculation.

LikeLike

## Jim Randell 12:14 pm

on3 March 2019 Permalink |Here’s my complete manual solution:

Writing:

We can start to examine divisors:

For

n = 2, it clearly divides the (6^36) term. Similarly forn = 3, 4, 6, 8, 9, 12, 16, ….For

n = 5, it doesn’t divide the (6^36) term, so let’s consider the value of(6^23310 mod 5):5 is prime, so we can use

Euler’s Theoremto reduce the exponentmod (p – 1):And if

(6^23310 mod 5) = 1then 5 divides the(6^23310 – 1)term.For

n = 7, we consider the value of(6^23310 mod 7):So 7 divides the

(6^23310 – 1)term.For

n = 10we already know 2 divides the(6^36)term and 5 divides the(6^23310 – 1)term.For

n = 11:So 11 divides the

(6^23310 – 1)term.For

n = 13:And 12 is equivalent to –1 mod 13, so 13 divides the

(6^23310 + 1)term.For

n = 14, we already have divisors of 2 and 7.For

n = 15, we already have divisors of 3 and 5.for

n = 17:9 is not equivalent to +1 or –1 mod 17, so 17 does not divide any of the terms, and gives our solution.

LikeLike