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 
Ellen Napier, 
Ruud, and 
Hugo, 
Alex.T.Sutherland, and 1 other are discussing. 
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: [To Be Revealed]
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}")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