Portsmouth MathJam November 2015

I addended the Portsmouth Maths Jam meeting this week (Tuesday 20125-11-17) to see what it was like. A principle activity was the Cross Number puzzle from issue 2 of Chalkdust and it is one of the questions from this puzzle that I want to discuss here.

The clue is/was 24 Across:
The lowest number $k$ such that when $3^k$ is divided by $k$ the remainder is $24$ (3 digits).

This is equivalent to asking for the smallest number $k$ for which there exists an integer $n$ such that: $3^k-24=nk$.

As the number in $3^k$ is $\lfloor k\log_{10}(3)\rfloor+1$ we are dealing with a LHS with between about 47 and 476 digits. This means we are dealing with numbers that are beyond the capabilities of the usual numerical maths packages sych as Matlab et al (though not beyond those of the arbitrary precision arithmetic of the symbolic maths packages such a Maxima, Mathematics, SymPy, .. which we will come back to later).

There was some discussion about approaches to this problem, one of which was that we look at in modular arithmetic to some suitable modulus. We discussed methods of evaluating large modular powers. However progress was problematic even using these idea as we really did not have suitable computational tools, and there was some reluctance to resort to what I would call "The Project Euler Approach" of applying some thought and mathematical knowledge to restrict the search space and then executing a computer assisted exhaustive search of the search space.

Later I decided to actually implement the modular search method, which involves writing or stealing code (or if you are lucky it comes fitted with numerical software tools). Here the basic idea is that:
$
\phantom{space this} (A \times B) \mbox{ mod } M = \bigl( (A  \mbox{ mod } M)\times (B  \mbox{ mod } M) \bigr)  \mbox{ mod } M
$
This idea may be translated into a powermod function with something like the following pseudo-code (note: this is a recursive function, in general iteration is more efficient than recursion):

function PowerMod(x,k,M)
//
//  function to eveluate x^k modulo M
//
  if k==1
      return mod(x,M)
  elseif k==0
      return 1  //Here I ought to deal with the special case x=0 but don't
  endif  

  if IsOdd(k)
      return mod( x*PowerMod( x,k-1,M) , M);
  else
      return mod( PowerMod( x,k/2,M)^2 , M);
  endif
endfunction

Now we observe that if $k,n$ are solutions of $3^k-24=nk$, then for every modulus $M$ we have $(3^k-24) \mbox{ mod } M=(nk)  \mbox{ mod } M$. So if for some modulus $M$ and candidate $k^*$ for $k$ we find that $(3^{k^*}-24) \mbox{ mod } M \ne (nk^*)  \mbox{ mod } M$ we can eliminate that candidate. So to search for a solution we search over a set candidates and moduli to see is some $n$ exists such that $(3^k-24) \mbox{ mod } M=(nk)  \mbox{ mod } M$ and use the results to thin the list of candidates to those that pass this test. We then repeat the process with a different modulus again thinning the list of candidates and so on until we either have a very short list that we can work with in the crossnumber puzzel, or better, we have a unique solution for $k$.

There is not much more to the code than that, and a few fussy details. Conducting a search with the odd numbers from 101 to 999 as candidates and test moduli from 2 to 10000 takes a few minutes on a modern PC and yields the result that $k=721$. As confirmation WolframAlpha when asked is  $(3^721-24)/721$ an integer confirms that it is.

As an excise in programming Maxima I wrote a function that loops over the list of candidates just testing if  $(3^721-24)/721$ is an integer and it returns one solution $k=721$, in a fraction of a second. Maybe this is where I should have started - though it took me longer to get the Maxima code working that it took to write a Matlab script to solve the problem by the method described above.

Having solved the problem I am left wondering if there is not a pencil and paper method of solving this problem, perhaps some regularity in the residues of $3^k-24$ for some modulus would allow us to find a solution? Also since the question asks for the smallest number with the given property we might ask for the next smallest (I have used the Maxima code to check, there are no other solutions less than 200,000), how many are there, is there some closed from for the solutions?

The next Portsmouth Mathsjam will take place on Tuesday the 15th of December at the King Street Tavern, Southsea.