|
Stated below are a few challenging problems. If you are first to publish a solution, let me know, and collect your reward! Or, if you find a short solution and you are quite sure it is correct and complete, send it to ck6@evansville.edu. If accepted, your proof will be published on this site - see, for example, Problem 8.
|
|
For many years, the sequence was thought to originate as indicated here:
William Kolakoski, "Self generating runs, Problem 5304," American Mathematical Monthly 72 (1965) 674. For a proof that the Kolakoski sequence is not periodic, see the same Monthly 73 (1966) 681-682.
However, it quite clearly occured earlier and can now be called the Oldenburger-Kolakoski sequence. It was discussed by Rufus Oldenburger, "Exponent trajectories in symbolic dynamics", Transactions of the American Mathematical Society 46 (1939), 453-466.
See also Kolakoski Sequence at MathWorld and Sequence A000002 at the Online Encyclopedia of Integer Sequences.
1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33, 46, . . . ?
Reward: $300.00. To generate the sequence, visit
Kimberling Sequence at MathWorld and Generator.
For a discussion and variant of the problem, see
Richard K. Guy, Unsolved Problems in Number Theory, second edition, Springer-Verlag, 1994.
The problem originates in
C. Kimberling, Problem 1615, Crux Mathematicorum 17 (1991) 44.
Consider the sequence (or infinite word)
R = (r1, r2, r3, . . . ) = 010001101011100100111101100000101... (commas deleted).
The first segment of length 1 to repeat is "0", at r1 and r3.
The first segment of length 2 to repeat "00", at r5.
The first segment of length 3 to repeat is "010", at r10.
The sequence R is constructed to avoid repetitions "as long as possible", as follows:
rn+1 = 1 if and only if
(r1, r2, . . . , rn, 0), but not (r1, r2, . . . , rn, 1),
has greater maximal repeated segment length than
(r1, r2, . . . , rn) has.
A finite string of 0's and 1's is called a word. Does every word occur in R?
If so, then it is easy to see that every word repeats infinitely many times in R, which is notable, since the rule for generating R tries to resist repetition.
This problem originates, in more general form, in
C. Kimberling, Problem 2289, Crux Mathematicorum 23 (1997) 501; [no solutions received: 24 (1998) 525].
The problem has been solved in the affirmative: the binary word R does indeed contain every binary word infinitely many times. The word R corresponds to a choice-sequence consisting of all 0's. Any binary sequence can serve as a choice-sequence; details are given in the reference cited just above.
The solution appears in Crux Mathematicorum 29 (2003) 320-321.
Like the theory of relativity, this problem has a special version and a general version. The special case originates in
C. Kimberling, Problem 2386, Crux Mathematicorum 24 (1998) 426 and is equivalent to the following:
Write "1". Skip some space and count the one 1 you've written by writing "1 1". Skip some more space and count the three 1's you've written so far by writing "3 1" - except write it with 3 above 1, like this:
3
1.
Skip some space, and count the four 1's and one 3 that you've written so far by writing
4 1
1 3.
Skip some space, and count what you've written so far by writing
6 2 1
1 3 4.
Skip some space, and count what you've written so far by writing
8 1 3 2 1
1 2 3 4 6.
If this procedure continues indefinitely, will every positive integer eventually be written?
Now for the general form of this problem. It's just like the special, except that we start with an arbitrary initial counting; that is, instead of starting with one 1, start with
a(1) a(2) a(3) . . . a(n)
b(1) b(2) b(3) . . . b(n),
where all the a(i) and b(i) are positive integers, and the b(i) are distinct. The problem is to prove or disprove that every positive integer will eventually be written during the counting procedure.
Let a1 = 1, and for n > 1, define an = [an-1/2] if this number is not in the set {0, a1, . . . , an-1}, and an = 3an-1 otherwise.
Does every positive integer occur exactly once in this sequence?
The problem originates in
C. Kimberling, Problem 2248, Crux Mathematicorum 26 (2000) 238; [no solutions received: 27 (2001) 345].
In the statement of the problem, the notation [x] means "the greatest integer that is <= x". Thus, the sequence (an) is generated by repeatedly multiplying by 3 and dividing by 2.
The MD sequence defined above begins like this: 1, 3, 9, 4, 2, 6, 18, 54, 27, 13, 39, 19, 57, 28, 14, 7, . . .
You can obtain another MD sequence by using 2 as multiplier and 3 as divisor:
1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 96, 32, 64, 21, 7, 14, 28, 9, 18, 36, . . .
Or, let m and d be any two relatively prime integers greater than 1. Does the resulting MD sequence contain every positive integer exactly once?
Mateusz Kwasnicki of Wroclaw University of Technology solved the MD problem in general and in the affirmative. See Crux Mathematicorum 30 (2004) 235-239.
Begin an array by writing the Fibonacci numbers: 1, 1, 2, 3, 5, 8, ... Start row 2 with the least unused positive integer, which is 4; follow 4 by 6, and finish the row using the Fibonacci recurrence (i.e., add the two most recent numbers to produce the next, so that row 2 starts with 4, 6, 10, 16, 26, 42). Start row 3 with the least unused, which is 7, follow 7 by 12, and then use the recurrence to produce 19, 31,.... Continue in this manner (the choice of second term in each new row is revealed below), getting rows 1 to 4 starting like this:
1 2 3 5 8 13 . . .
4 6 10 16 26 42 . . .
7 12 19 31 50 81 . . .
9 14 23 37 60 97 . . .
.
.
.
Here is the recipe for the second number in each row: let r be the golden ratio, (1+sqrt(5))/2, let i be the number of the row, and let x be the first number in the row; then the second number is [rx] if i is even, and it is [rx]+1 if i is odd.
For example, row 5 starts with the least unused, which is x=11, and this is followed by [11r]+1, which is 18.
Is every number is column 2 even?
In anticipation that the answer is yes, the array is introduced as the Even Second Column Array in
C. Kimberling, "The First Column of an Interspersion," The Fibonacci Quarterly 32 (1994) 301-315.
Michael Behrend proved that the answer is yes: Proof that they are all even.
For any sequence A = (a(0), a(1), a(2), . . . ) of positive real numbers, create a sequence B from A as follows: let b(0) = a(0) and for k>0, let
U = [a(2k-1)]2, V = a(2k), W = 4b(k-1),
b(k) = V - U/W. (Assume for each k that W is not zero.)
For a couple of easy examples, start with A = (1, 2, 3, 4, . . . ) and A = (1, 1, 1, 1, . . . ).
Here's the unsolved problem: determine, with proof, conditions on c and d for which the arithmetic sequence A = (c, c + d, c + 2d, c + 3d, . . .) yields b(k) > 0 for every k.
Peter Kosinar found a necessary and sufficient condition to be 0 < d <= c. He also proved that if d > c, then the sequence B contains one and only one negative number: On The Mysterious B Sequence.
For an associated array of numbers, see A186158 at the Online Encyclopedia of Integer Sequences.
Reward: $50.00 (Paid).
There is a unique shape of triangle ABC that is both side-golden and angle-golden (in contrast to a single shape of rectangle that is called the golden rectangle). The angles of ABC are B, tB and π - B - tB, where t is the golden ratio. The terms "side-golden" and "angle-golden" refer to partitionings of ABC, each in a manner that matches the continued fraction [1, 1, 1, . . . ] of t.
The special number B is the number between 0 and π such that sin(t2B) = t sin(B). A number close to B is
0.65740548297653259238096854152939712654149594648783937,
which, as an angle, is between 37 and 38 degrees.
Can you prove, or disprove, that B is irrational?
Reference: A152149 in the Online Encyclopedia of Integer Sequences.
Matthew Albano proved that this is an easy consequence of the Lindemann-Weierstrass theorem: that if x(0), x(1), . . . , x(m) are distinct algebraic numbers, then the numbers
ex(0), ex(1), . . . , ex(m)
are linearly independent over the algebraic numbers. (See, for example, Theorem 3.4, page 44, of Making Transcendence Transparent: an Intuitive Approach to Classical Transcendental Number Theory, by Edward B. Burger and Rober Tubbs, Springer, 2004.)
Write sin(t2B) - t sin B = 0, and suppose that B is algebraic. The identity
sin A = (eiA - e- iA)/2i
then gives
eit2B - e - it2B - teiB + te- iB = 0.
Since the coefficients and exponents are all algebraic, this equation implies, by the theorem, that the numbers it2B, - it2B, iB, and -iB are not distinct. This contradiction proves that B is transcendental.
Let L = (1, 3, 4, 6, 8, . . . ) be the lower Wythoff sequence, A000201, and let U be the complement of L; i.e., U = (2, 5, 7, 10, . . . ), the upper Wythoff sequence, A001950.
For each odd U(n), let L(m) be the least number in L such that after swapping U(n) and L(m), the resulting new sequences are both increasing. The resulting sequence, called a "swappage" of L, is
V = (2, 4, 6, 10, 12, 14, 18, 20, 22, 26, . . . ) = A141104.
Let S(n) = (1/2)V(n) for every n. Is the complement of S (in the set of nonnegative integers) the same set of numbers that comprise the sequence A004976 ?
Russo and Schwiebert prove that the answer is yes in their article, "Beatty Sequences, Fibonacci Sequences, and the Golden Ratio," The Fibonacci Quarterly49 (2011) 151-154.
Find parametric equations for a simple closed curve of length 4π on the unit sphere which minimizes the mean spherical distance from the curve to the sphere; the solution must include proof of minimization. Can you solve this problem with arbitrary L > 2π instead of 4π?
There seems to be little precedent for this problem. A few recently studied spherical curves (which probably do not minimize the mean distance) can be viewed at Gallery of Space Curves Made from Circles and Gallery of Bishop Curves and Other Spherical Curves.
For any sequence s consisting of 1's and 2's, let r(s) denote the length of the nth run of same symbols in s. There is a unique nontrivial sequence s such that s(1) = 1 and r(r(s(n))) = s(n) for all n. Successive terms of s and r, easily generated, are shown here:
s = (1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, . . .)
r(s) = (2, 1, 2, 2, 1, 2, 1, 1, 2 , 2 ,1, 2, 2, 1, 1, 2, 1, . . .) .
Here's the problem: prove or disprove that every segment of r(s) is a segment s.
For example, the initial segment 1121 of s occurs in r(s) beginning at the 14th term.
This problem first appeared as Problem 90 in Mathematicsche Semesterberichte 44 (1997) 94-95. More terms are given at A025142 and A025143.
First, decree that T(1,1) = 1. Then for n > 0, let S(n) = {(i,j) : 1 <= i <= n, 1 <= j <= n},
and let
T(1,n+1) = least positive integer not among T(i,j) for (i,j) in S(n);
T(n+1,1) = least positive integer not among T(i,j) for (i,j) in S(n) and not (T,n+1);
T(m,n+1) = T(m,1)*T(1,n+1).
These rules generate an array T which starts out like this:
| 1 | 2 | 4 | 7 | 9 | 13 | 15 | 18 | 23 | 25 | 29 |
| 3 | 6 | 12 | 21 | 27 | 39 | 45 | 54 | 69 | 75 | 87 |
| 5 | 10 | 20 | 35 | 45 | 65 | 75 | 90 | 115 | 125 | 145 |
| 8 | 16 | 32 | 56 | 72 | 104 | 120 | 144 | 184 | 200 | 232 |
| 11 | 22 | 44 | 77 | 99 | 143 | 165 | 198 | 253 | 275 | 319 |
Every prime is in row 1 of T or column 1, but not both.
The difference sequence of row 1 starts with
1,2,3,2,4,2,3,5,2,4,2,5,4,2,4,3,2,4,3,2,2,4,4,7,2,3,2,4,3,5,5,3,4.
Here's the problem: prove (or disprove) that this difference sequence bounded.
More terms of the array T and its first row are given at A129258 and A129259.
This problem involves an algorithm the "self-generates" a sequence of nonnegative integers and a sequence of integers.
First, some notation: let a(1) = 1 and d(1) = 0. For k > 0, let x = a(k), and let
P(k) = {a(1), a(2), . . . , a(k)}, and D(k) = {d(1), d(2), . . . , d(k)}.
Step 1. If there is a negative integer h not in D(k) such that x + h is not in P(k), and x > 0, then let d(k+1) be the greatest such h, let a(k+1) = x + h, and return to Step 1; otherwise do Step 2.
Step 2. Let h be the least positive integer not in D(k) such that x + h is not in P(k). Let a(k+1) = x + h and d(k+1) = h, and do Step 1.
Problems and Rewards: $25 for proof (or $20 for counterexample) of each of the following propositions.
(1) a(k) runs through all the positive integers;
(2) d(k) runs through all the integers;
(3) if d(k) > 0, then d(k+1) > 0 or d(k+2) > 0 or d(k+3) > 0;
(4) if d(k) < 0, then d(k+1) < 0 or d(k+2) < 0 or d(k+3) < 0.
The sequence (a(k)) begins with 1,2,4,3,6,10,8,5,11,7,12,19,14,22,16,9.
The sequence (d(k)) begins with 0,1,2,-1,3,4,-2,-3,6,-4,5,7,-5,8,-6,-7,9.
More terms of the sequences are given at A131388 and A131389.
Let G = (1 + 51/2)/2 and f(n) = floor(n2G) - n floor(nG), for n = 1,2,3, . . . .
Examples:
f(n) = 0 for n = 0, 1, 2, 5, 13, 34, . . .
f(n) = 1 for n = 4, 10, 16, 68, 178, . . .
f(n) = 2 for n = 3, 7, 18, 47, 123, . . .
Reward of $20 for a proof that f(n) is never 3. (Paid)
Michael Behrend proved that the answer is yes: Proof that they are all even.
Consider the following array of all the natural numbers:
| 1 | 2 | 4 | 7 | 11 | 16 | 22 | 29 | 37 | 46 | 56 |
| 3 | 5 | 8 | 12 | 17 | 23 | 30 | 38 | 47 | 57 | 68 |
| 6 | 9 | 13 | 18 | 24 | 31 | 39 | 48 | 58 | 69 | 81 |
| 10 | 14 | 19 | 25 | 32 | 40 | 49 | 59 | 70 | 82 | 95 |
| 15 | 20 | 26 | 33 | 41 | 50 | 60 | 71 | 83 | 96 | 110 |
This array is discussed at A000027 and A185787.
Prove or disprove that every row contains infinitely many primes.
Note added (March 25 2012): the problem is hard. Charles Greathouse writes that it reduces to the Hardy-Littlewood Conjecture F...it's not hard to show that each column corresponds to an integer-valued polynomial satisfying the requirements of the conjecture (the discriminant is always negative and hence nonsquare); for total conformance to the conjecture as printed replace it with two polynomials, one for even columns and one for odd. "So," he writes, "I don't expect to see a proof of this one any time soon."
Pedja Terzic calls attention to rows instead of columns: the nth term of the first row is given by an = (n2 - n + 2)/2, so that for n=2k, we have a2k = P(k)=2k2 - k + 1 and for n=2k-1, we have a2k-1 = Q(k)=2k2 - 3k + 2. Both P(k) and Q(k) are irreducible over the integers. Also, GCD(P(1), P(2),...)=1 and GCD(Q(1), Q(2),...)=1. Therefore, according to the Bunyakowsky conjecture, each of the sequences (P(k)) and (Q(k)) includes infinitely many primes. The same holds for all the other rows. So, one should prove or disprove the Bunyakowsky conjecture.
Prove or disprove that if r is an irrational number between 1 and 2, then there are infinitely many primes of the form floor(n*r).
This problem is stated at A025142.
Note added (March 25 2012): a proof is known. Michael Behrend notes that a proof can be found in I. M. Vinogradov, The Method of Trigonometrical Sums in the Theory of Numbers, Interscience Publishers, London and New York, 1954, page 180. There, Vinogradov writes that "the result [that if x is any fixed irrational number then the fractional parts of nx are uniformly distributed between 0 and 1] can be expressed in another form, as was suggested by Professor Heilbronn: [if x>1 and x is not an integer, the numbers [nx] include infinitely many primes]."
Let r denote the golden ratio, (1+sqrt(5))/2, and let [ ] denote the floor function. For fixed n, let u(k)=[k*r^n], let v(k)=[k*r]^n, and let w(k)=[v(k)/k^(n-1)]. We can expect w to have about the same growth-rate as u.
Prove or disprove that for every fixed n>0, as k ranges through all the positive integers, there is a number M such that u(k)-w(k) takes each of the values 1,2,...,M infinitely many times, and u(k)-w(k)<=M. (Can you formulate M as a function of n? Generalize for other numbers r?)
Michael Behrend proved that M exists for r = (1+sqrt(5))/2 and that there are other value of r for which there is no such M. The solution: Special M
In how many ways can the numbers 1, 2, ..., n(n+1)/2 be arranged in a triangular format with interlacing rows? That is, if a(i,j) denotes the jth number in row i, then a(i,j) is between a(i+1,j) and a(i+1,j+1), as in the following examples (for n = 3):
| 3 | ||||
| 2 | 5 | |||
| 1 | 4 | 6 |
| 3 | | |||
| 5 | 2 | |||
| 6 | 1 | 4 |
| 4 | ||||
| 3 | 5 | |||
| 2 | 6 | 1 |
Noam Elkies proved that there is a point X in the plane of an arbitrary ABC such that the triangles AXB, BXC, CXA have congruent incircles. Find reasonable barycentric coordinates for X. (The point X is listed as X(5394) in the Encyclopedia of Triangle Centers: ETC - Part 3)
Solution by Shi Yong, Shanghai, China, January 3, 2013
Let DEF be the Morley triangle of ABC, and label the vertices, A, B, C, D, E, F as shown in the following pictures: Picture 1 and Picture 2
At vertex F, place the origin of the complex plane, with axes scaled so that the foot of the altitude of F on side AB is the point 1+0*i. Write angles as u = BAC, v = CBA, w = ABC = π - u - v. Then
a = - cos(2u/3) + i*sin(2u/3) and b = - cos(2v/3) - i sin(2v/3).
Rotation, translation, and dilation yield A = 2/(a + 1), B = 2/(b + 1), C = 2(a + b - 1)/(a2 + ab + b2), as shown in Picture 1.
Let w = (1 + 31/2i)/2.
P1 = a3b3 + a2b4 + ab4 + a4 - a3b - ab3 + b4 + a2b + b3 + ab
The point Z = X(5390), shown as Zhao in Picture 1 and as X(5390) in Picture 2, is given by
Define A' by applying the transformations a -> 1/a, b -> 1/b, c -> 1/c in the formula for A. Likewise, define B' from B, C' from C, P'1 from P1, Q'1 from Q1, P'2 from P2, and Q'2 from Q2.
It will be convenient to abbreviate X(5390) as Z. Define Z' by applying to Z the transformations a -> 1/a, b -> 1/b, c -> 1/c, P1 -> P'1, Q1 -> Q'1, P2 -> P'2, Q2 -> Q'2.
Let x : y : z be barycentric coordinates for Z. Solving the system
Ax + By + Cz = Z, A'x + B'y + C'z = Z', x + y + z = 1
gives
x = (a + 1)(Zb3 - 2b2 + 2b - Z')/(2(b - a)(b2 - b + 1))
With a computer algebra system, it can be shown that the complex conjugates of x, y, z are equal to x, y, z, respectively; that is, they are real-valued.
Q1 = (a - b)(a3b2 + a2b3 + a3b + a2b2 + ab3 + a2 + b2)
P2 = ab2 + a2 - 3ab + b2 + b
Q2 = (a - b)(ab + 1)
Z = 2(Q1 + wP1 )/(Q2 + wP2)/((a + 1)(b + 1)(a2 + ab + b2))
y = (b + 1)(Za3 - 2a2 + 2a - Z')/(2(a - b)(a2 - a + 1))
z = (a2 + ab + b2)(2 - Z - Z')/(2(a2 - a + 1)(b2 - b + 1))
For fixed positive integer m, let a(n) be the increasing sequence of nonnegative integers k such that
Prove or disprove that a(n) is a homogeneous linear recurrence sequence.
Example: for m = 3, see sequence A219085 in the Online Encyclopedia of Integer Sequences
David Moews proved for each m > 0, the sequence a(n) is a linear recurrence sequence (LRS), because it is the sum of a polynomial and a periodic sequence, and both of these are LRSs. A proof follows. Starting with the formula in the Comments section of A219085,
If m is even the upper bound on the order can be lowered. Suppose that m is divisible by 2k for some k > 0. Then (2n + 1)m mod 2m depends only on n mod 2m-k-1, so that the sequence frac((n + 1/2)m) is annihilated by E2m-k-1 - 1. Also, the value of (2n + 1)m mod 2m is unchanged if n is replaced by 2m-k-1 - n - 1. If m > 3, this replacement interchanges even and odd values of n, so that the sum of the residues coming from even values of n equals that coming from odd values. This shows that the sequence frac((n + 1/2)m) is annihilated by
Let U(n) and V(n) be the number terms in the Lucas and Zeckendorf representations, respectively, of all the numbers 1,2,...,n. Prove or disprove that V(n) >= U(n) for all n and that V(n) = U(n) for infinitely many n.
Michael Behrend proved both propositions: Lucas and Zeckendorf representations
Characterize the numbers r for which the sequence floor(n*r) contains a homogeneous linearly recurrent subsequence.
Let f(n) = 1/(H(n) - g - log n), where H(n) = 1+ 1/2 + 1/3 + ... + 1/n and g is the Euler-Mascheroni constant. Prove that lim(f(n) - 2n) = 1/3.
SOLVED by Goudout Élie, August 2013
The asymptotic equation H(n) = g + log n + 1/(2n) - 1/(12n˛) + o(1/n˛) is proved, for example, in Graham, Knuth, and Patashnik, Concrete Mathematics, p. 466. Then
1/(H(n) - g - log n) = 2n/(1 - 1/(6n) + o(1/n)) = 2n*(1 + 1/(6n) + o(1/n))
for big values of n, so that 1/(H(n) - g - log n) = 2n + 1/3 + o(1) for big values of n.
For connections to the joint ranking of the harmonic numbers and the numbers g + log k for k>=1, see A226894 at the Online Encyclopedia of Integer Sequences.
Picture1.jpg){kind=link}
Picture2.jpg){kind=link}