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:

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 2^m 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 a_i = 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#:

Checking the conjecture

   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[182];

  57:              int mark = 1;

  58:              A[0] = 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:  }

~bye

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.

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(2^m / 3^k ) mod 6 = 3 .