# An arithmetic conjecture

An arithmetic conjecture from an old discussion in the newsgroup de.sci.mathematik:

For all m > 26 there exist a k > 0 such that [2^m / 3^k] mod 6 = 3.

Given m let s(m) denote the smallest k such that the conjecture holds  - assuming existence - or 0 otherwise.

0,0,0,0,0,2,1,0,3,0,0,3,1,3,0,0,2,0,1,5,4,12,7,2,1,11,0,15,10,4,1,4,10,3,2,9,1,..

This is  A157409 at OEIS. Further let t(m) be the maximum of the s(i) for all i <= m. Now list only those pairs m, t(m) where t(m) increases. Maple code for m > 26:

```maxK := 1; pow2 := 2^26;
for m from 27 to 1000 do
k := 1; pow3 := 3; pow2 := pow2 + pow2;
while modp(iquo(pow2,pow3),6) <> 3 do
pow3 := 3*pow3: k := k+1; od;
if k > maxK then maxK := k; print(m, maxK); fi;
od:
```
 M 5 8 19 21 27 49 110 118 165 2769 2837 3661 14354 59913 1786453 2702893 2712849 K 2 3 5 12 15 21 29 34 58 61 65 70 74 103 112 117 121

To paraphrase the evidence of these sequences: "You quickly find such a k, even for large m."

When I mentioned the conjecture on SeqFans mailing list David Wilson answered:

To my knowledge, no one knows how to prove your statement. Without getting heavily into it, this problem belongs to a class of problems with problems like:

Does every sufficiently large power of 2 include the digit 0 in base 10?

which statistically are true with probability 1, but have not to my knowledge been proved.

A first result is an observation of Wolfgang Kirschenhofer. Basically it says that the conjecture is equivalent to the existence of a certain split of the expansion of 2m in base 3. k is here the position of the 0. For example this split is

[2,2,1]0 [0,0,0,2,2,0,1,1,2,2,1,1,1,0,1,1,2] for m = 32 and
[1,2]0 [1,0,0,0,1,2,1,2,2,1,2,0,0,0,1,2,2,1,1] for m = 33. A simple corollary is: If m >= 30 is a multiple of 6 then there exists a k > 0 such that [2^m / 3^k] mod 6 = 3. (Proof: Choose k = 1 in Kirschenhofer's theorem.) So at least we know now that the conjecture is true for infinitely many cases :-)

In fact Kirschenhofer looked at the ai = 1 with i > k. Our variant (i < k) is much better suited for checking the conjecture since it turned out that the k`s are small compared to the m`s. Based on this  observation we can abstain from expanding 2^m to the full length and narrow the expansion to a small initial segment while disregarding the higher digits. This results in a much improved algorithm, which also needs no big-integer library. Below an implementation in C#:

`   1:  // Author: Peter Luschny, 2009-03-03`
`   2:  // For more information see:`
`   3:  // http://www.luschny.de/math/vermutung.html`
`   4:  // Thanks to all contributors at de.sci.mathematik,`
`   5:  // especially to Wolfgang Kirschenhofer and Klaus Nagel.`
`   6:   `
`   7:  using System;`
`   8:  using System.Diagnostics;`
`   9:   `
`  10:  namespace zahlvermutung`
`  11:  {`
`  12:      class Program`
`  13:      {`
`  14:          static void Main(string[] args)`
`  15:          {`
`  16:              Stopwatch watch = new Stopwatch();`
`  17:              watch.Start();`
`  18:              // The value of this constant is 2,147,483,647`
`                   // that is 2^31-1.`
`  19:              conjecture(int.MaxValue);`
`  20:              watch.Stop();`
`  21:              Console.WriteLine("Elapsed time: " + `
`                                      watch.Elapsed.ToString());`
`  22:              Console.WriteLine("~ bye ~");`
`  23:              Console.ReadLine();`
`  24:          }`
`  25:   `
`  26:          static int maxK = 0;`
`  27:   `
`  28:          static void check(int[] A, int m, int b)`
`  29:          {`
`  30:              var one = 0;`
`  31:   `
`  32:              for (var i = 0; i < b; i++)`
`  33:              {`
`  34:                  if (A[i] == 1)`
`  35:                  {`
`  36:                      one = one + 1;`
`  37:                  }`
`  38:                  else if (A[i] == 0)`
`  39:                  {`
`  40:                      if (one % 2 == 1)`
`  41:                      {`
`  42:                          if (i > maxK)`
`  43:                          {`
`  44:                              maxK = i;`
`  45:                              Console.WriteLine(m + " : " + maxK);`
`  46:                          }`
`  47:                          return;`
`  48:                      }`
`  49:                  }`
`  50:              }`
`  51:              Console.WriteLine(m + " : failed");`
`  52:          }`
`  53:   `
`  54:          static void conjecture(int n)`
`  55:          {`
`  56:              int[] A = new int;`
`  57:              int mark = 1;`
`  58:              A = 1; maxK = 0;`
`  59:   `
`  60:              for (var m = 1; m < n; m++)`
`  61:              {`
`  62:                  int r = 0;`
`  63:                  mark = Math.Min(mark, 180);`
`  64:                  for (var i = 0; i < mark; i++)`
`  65:                  {`
`  66:                      var Ai = 2 * A[i] + r;`
`  67:                      if (Ai >= 3) { A[i] = Ai - 3; r = 1; }`
`  68:                      else { A[i] = Ai; r = 0; }`
`  69:                  }`
`  70:                  `
`  71:                  if (r > 0) { A[mark] = r; mark++; }`
`  72:                  check(A, m, mark);`
`  73:              }`
`  74:          }`
`  75:      }`
`  76:  }`

With this algorithm I was able to check the conjecture up to m = 2^31 = 2,147,483,648 in less than 45 minutes on an PC vintage 2005. The above table continues as shown below.

 M 7,384,247 21,219,075 193,702,717 899,019,601 1,305,797,743 K 122 130 153 156 159
 M 8,155,079,481 9,856,426,495 15,164,102,636 28,051,390,987 K 168 169 170 177

This table also implies that the conjecture holds true for all m <= 28,051,390,987.

## Eine zahlentheoretische Vermutung

Seien a, b natürliche Zahlen, die keinen gemeinsamen Teiler besitzen, m und k natürliche Zahlen, m >= 0, k > 0, dann betrachte man

[a^m / b^k] mod ab = c, wobei c = a oder c = b.   (*)

[x] ist hierbei die größte ganze Zahl kleiner oder gleich x und 'mod' bezeichne den Rest bei der ganzzahligen Division. Die Frage ist, ob es zu gegebenen a, b, c und m stets ein k > 0 gibt, so dass diese Relation erfüllt ist. Die Vermutung besagt, dass für den Spezialfall a = 2, b = 3 und c = b für alle m > 26 ein k > 0 existiert, so dass (*) gilt. Einfacher gesagt, die Vermutung ist:

Für alle m > 26 existiert ein k > 0, so dass gilt

floor(2m / 3k ) mod 6 = 3 .