Teaser 3331: Salarium solace
From The Sunday Times, 26th July 2026 [link] [link]
During his last campaign in Germany, Centurion Ulpius lost more than one-third of his original 80 legionaries. The remaining number of men was prime. On their return to Rome, the Legate ordered his Prefect to share out the leftover salt stock to Ulpius’s remaining men, as a reward for their bravery.
The Prefect must ensure each man receives an identical amount. Using his scales he could accurately halve any quantity of salt. He divided the initial amount into two equal piles repeatedly until the number of piles exceeded the number of men. The men then received a pile each. The remaining piles were again each halved and distributed in the same way until only one pile remained.
The Prefect returned home with this pile, one in 16,384 of the original stock.
How many of Ulpius’s men returned to Rome?
[teaser3331]
Frits and 
Tony Smith, 
Hugo, 
Mark Valentine are discussing. 
Brian Gladman are discussing. 
Ellen Napier and 
GeoffR and 
S2T2 
Jim Randell 6:25 am on 26 July 2026 Permalink |
Here is a constructive solution that follows the procedure for primes up to 53.
This Python program runs in 65ms. (Internal runtime is 68µs).
from enigma import (primes, printf) # target fraction (1/F) F = 16384 # perform the procedure def solve(n, F=F): # initial number of piles (= k), and fraction for each pile (= 1/f) k = f = 1 while f < F: # increase the number of piles until it exceeds the number of men while not (k > n): k *= 2 f *= 2 # n piles are distributed to the men k -= n # are we done? if k == 1: return f # consider possible remaining number of men (= n) for n in primes.between(2, 53): f = solve(n) if f == F: printf("n={n} -> f={f}")Solution: 43 of Ulpius’ men returned to Rome.
Each man received: 1/64 + 1/256 + 1/512 + 1/1024 + 1/2048 + 1/4096 + 1/16384 = 381/16384 of the original amount of salt.
So the total amount of salt distributed to the men was: 43 × 381/16384 = 16383/16384. Leaving 1/16384 remaining.
Manually:
The salt is divided into 16384 equal portions, of which 1 is retained.
So the remaining 16383 portions are divided equally between the (prime number) of men.
It is straightforward to determine the prime factorisation of 16383 (= 2^14 − 1):
We can do trial division of primes up to 11 on each factor (or note that 127 is a Mersenne prime, and 129 is clearly divisible by 3), so the prime factorisation of 16383 is:
Of these prime factors only 3 and 43 are viable candidate primes for the number of men (i.e. less than (2/3) × 80 = 53 + 1/3).
For each case we can calculate the multiplicative order of 2 modulo n (we can use the procedure described in the puzzle text to do this, and count the number of times the piles are divided):
And only 43 gives the required answer of 14.
LikeLike
Jim Randell 8:50 am on 26 July 2026 Permalink |
For n men we are are looking to find the multiplicative order of 2 modulo n, i.e. the smallest k such that 2^k mod n = 1 [@wikipedia]. And we are interested in the case where k = 14 (as 2^14 = 16384).
This gives rise to a shorter program:
from enigma import (primes, irange, printf) # target fraction (1/2^M) M = 14 # 2^14 = 16384 # find k st. 2^k mod n = 1 def solve(n, m=M): for k in irange(1, m): if pow(2, k, n) == 1: return k # consider possible number of men (= n) for n in primes.between(2, 53): k = solve(n) if k == M: printf("n={n} -> k={k}")or even shorter:
from enigma import (primes, irange, printf) # target fraction (1/2^M) M = 14 F = 2**M # consider possible number of men (= n) for n in primes.between(2, 53): if F % n == 1 and all(pow(2, k, n) != 1 for k in irange(1, M - 1)): printf("n={n} -> k={M}")See also: Teaser 2406.
LikeLike
Frits 1:16 pm on 26 July 2026 Permalink |
My first attempt was pretty similar to Jim’s first program.
I rewrote it a little bit in order not to calculate powers for every prime number.
from math import log N = 16384 # remaining number of men (< 2/3) was prime P = {3, 5, 7} P |= {2} | {x for x in range(11, (2 * 80 - 1) // 3 + 1, 2) if all(x % p for p in P)} # powers of 2 (only highest power > remaining number of men) pow2 = [(i, 2**i)for i in range(1, 7)] target = log(N, 2) # assuming N is a power of 2 # return first power to overshoot the prime number nxt = lambda n, p: next((i, pow) for i, pow in pow2 if n * pow > p) # remaining number of men for p in P: n, k = 1, 0 # perform repeated doubling of piles while k < target: k_, n_ = nxt(n, p) k += k_ # until only one pile remained if (n := n * n_ - p) == 1: break # check if only one pile remained if k == target and n == 1: print(f"answer: {p}")LikeLike