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[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: }
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.
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 .