-------------------------------------------------------------------- The conjecture is true. A nice short paper about this is "Linear Recurrence Relations", by J. L. Brenner, Amer. Math. Monthly, Vol. 61 (1954), 171-173. Let me know if you want more details. Nice website! Best regards, Tony Noe -------------------------------------------------------------------- -------------------------------------------------------------------- -------------------------------------------------------------------- For any integer n, let S={[a,b,c]:0<=a,b,cS be the map that takes [a,b,c] to [b,c,a+b+c] (the addition being done modulo n). Further, let g:S->S be the map that takes [a,b,c] to [c-(a+b),a,b] (the subtraction and addition being done modulo n). It is clear that if x=[0,1,1] then f^k(x)=[T(k),T(k+1),T(k+2)] (T(z) representing the zth tribonacci number modulo n). Further it is evident that since S is finite, there is some element y of S such that the set V={k:f^k(x)=y} is infinite. Now note that g.f is the identity map. Thus if k is the smallest element of V, g^k(y)=g^k(f^k(x))=x. Thus if k2 is the second smallest element of V, f^(k2-k)(x)=g^kf^k2(x)=g^k(y)=x. Thus T(k2-k)=0 modulo n. Luke Pebody -------------------------------------------------------------------- Dear Ed, I think I have an easy proof that the answer is "yes". Let n be an integer. Let G be a directed graph whose vertices are elements of Z_n x Z_n x Z_n. For each vertex (a,b,c), define one edge coming out, passing to (b,c,d) where d = a+b+c mod n. Lemma 1 : There does not exist a vertex with two incoming edges. Proof : If (b,c,d) has two incoming edges, they must be (a,b,c) and (a',b,c), where d = a+b+c = a'+b+c mod n, that is, a = a' = d-b-c mod n. Lemma 2 : Every vertex has exactly one incoming edge and exactly one outgoing edge. Proof : Given a vertex (b,c,d) the edge going out is uniquely defined. Likewise, there is an edge coming in to (b,c,d) from (d-b-c mod n, b,c), also uniquely defined. Lemma 3 : G is a union of cycles. Proof : Follows easily from Lemma 2 and the fact that there are a finite number of vertices. It follows therefore that the vertex (0,1,1) is in a cycle. Following the edges from (0,1,1) will eventually lead back to (0,1,1). However, this is equivalent to looking at three-term 'windows' of the tribonacci sequence modulo n. For example, the tribonacci sequence starts : 0,1,1,2,4,7,13,24,44,... mod 10, this is : 0,1,1,2,4,7,3,4,4,... In the graph (n=10): (0,1,1) -> (1,1,2) -> (1,2,4) -> (2,4,7) -> (4,7,3) -> (7,3,4) -> (3,4,4) -> ... For n=10, this comes back to (0,1,1) after 124 steps. Since the path through the graph eventually comes back round to (0,1,1), it follows that eventually there is a tribonacci number which equals 0 modulo n, that is, it is a multiple of n. I am wondering how many steps before it gets back to (0,1,1)? I have tested it on a few prime numbers : 2 : 4 3 : 13 5 : 31 7 : 48 11 : 110 13 : 168 17 : 96 19 : 360 23 : 553 29 : 140 31 : 331 All these, except for p=2 and p=11, seem to be factors of either p^2-1 or p^3-1. Interesting. Ok, enough for now. Yours, Michael Hartley -------------------------------------------------------------------- Tribonacci numbers: T(0)=0, T(1)=1, T(2)=1, T(n+3) = T(n+2) + T(n+1) + T(n) Jonathan vos Post conjectures that every integer is a factor of a Tribonacci number (other than T(0)). It's quite obvious; no doubt you've received twenty proofs by now. Consider any positive divisor D, and the sequence D(N) = T(N) modulo D. Then D(n+3) = D(n+2) + D(n+1) + D(n) modulo D. There are at most D^3 possible triplets, so eventually one gets a repetition of triplets. Let A and B be the first indices such that B > A, D(A) = D(B), D(A+1) = D(B+1), and D(A+2) = D(B+2). If A is positive, one can compute modulo D, D(A-1) = D(A+2) - D(A+1) - D(A) and D(B-1) = D(B+2) - D(B+1) - D(B); so D(A-1) and D(B-1) are equal! A and B aren't the first indices, and the contradiction shows that A is zero. Since A is zero, T(B) modulo D = D(B) = D(A) = D(0) = 0; so D divides T(B). -- The proof-idea works for Fibonacci's, "quadronaccis", and any Lucas-like sequence which starts at zero. -- Don Reble -------------------------------------------------------------------- The conjecture is true. The sketch of the proof is as follows. Note that we can set T_0=0. Tribonacci sequence can be continued forwards as well as backwards. Say we are interested in a term divisible by d. Then we do all computations modulo d and reduced terms of the sequence are from the finite set 0,1,2,...,d-1. Therefore we will find a triple of consecutive terms a,b,c repeated at different positions. Therefore Tribonacci sequence is periodic modulo d, with period length at most d^3. Since T_0=0 we will find a term divisible by d after each period. Yours, Jarek Wroblewski -------------------------------------------------------------------- Jonathan vos Post conjectures that every integer is a factor of a Tribonacci number. For example, 10 is a factor of 35890, the 19th Tribonacci number, by the method at MathWorld. (Where Tribonacci numbers are 0, 1, 1, 2, 4, 7, 13, ... generated by T(n)=T(n-1)+T(n-2)+T(n-3).) Proof that an arbitrary integer n is a factor of some Tribonacci number: Consider the Tribonacci numbers modulo n. Each triple of consecutive numbers generates the following number in the sequence, so there is a set sequence of these triples of consecutive numbers, such as (0,1,1), (1,1,0), (1,0,0), (0,0,1), (0,1,1), ... for n=2. Since there are only n^3 possible triples, the sequence must eventually repeat a term, and since each term is determined only by the preceding one, the entire sequence repeats at this point. The sequence can also be run backward, taking T(n-3) = T(n) - T(n-1) - T(n-2) (again mod n). Each triple has a unique predecessor, and the sequence must repeat this way as well, so the repeating sequence includes all terms including the (0,1,1) at the beginning. The second appearance of (0,1,1) in the mod n Tribonacci sequence corresponds to a Tribonacci number of which n is a factor. Furthermore, since there are only n^3 possible triples, the first such number occurs no later than T(n^3 + 1). Indeed, it must come before that; if the repeating sequence of triples includes (0,1,1) and every triple of three non-zeroes before the next triple including zero, then the first such number occurs at position T((n-1)^3 + 4). I also note that my proof works for a great many other Fibonacci-like sequences. It needs the reversibility of the sequence mod n, and the 0 in the sequence, possibly by extending the sequence backward. And oops, fix that reuse of n before you post the solution. Regarding the reversibility, a sequence like F(k) = F(k-1) + 2 F(k-2) would not work, because when you reverse it, 2 F(k-2) = F(k) - F(k-1) has two possible values for F(k-2) mod n. As a result, it is possible that running the sequence backward leaves the repeating cycle, and since it can run into fractional values when F(k) - F(k-1) is not divisible by 2, it is also not required that it ever enters another repeating cycle. The result is that this sequence might enter a repeating cycle mod n which does not include the 0. The example sequence does so for n=2: 0 1 1 3 5 11 21 ... (all following terms are odd, because they are the sum of an odd and an even number). If the coefficient of the earliest term in the sequence used in the recursion is 1 or -1, it should work. Joseph DeVincentis -------------------------------------------------------------------- Jonathan vos Post conjectures that every integer is a factor of a Tribonacci number . For example, 10 is a factor of 35890, the 19th Tribonacci number, by the method at MathWorld. The conjecture has been verified to 500 -- seems quite chaotic. Can anyone prove this conjecture, or verify it up to some big number? Observation 1: The Fibonacci numbers are periodic modulo n, where n is any positive integer. If the period is m, then Fibonacci[m] is divisible by n, because Fibonacc[0]==0. Proof: The periodicity is from the pigeonhole principle. There are only n^2 possibilities for {Mod[Fibonacci[k], n], Mod[Fibonacci[k+1], n]}. Furthermore, there is no nonperiodic "tail" at the very beginning because the operation Fibonacci[k+1] == Fibonacci[k]+Fibonacci[k-1] is reversible (i.e. the Fibonacci numbers could be defined over all integers so there is no beginning to be worried about). This proof is cribbed from http://www.math.temple.edu/~renault/fibonacci/fib.html. Observation 2: The exact same proof works for Tribonacci numbers and n-step Fibonacci numbers. John Renze --------------------------------------------------------------------- Regarding the Tribonacci number conjecture, I’ve verified up to 1680 before I get an overflow at about 2600 digits, at Tribonacci num 9794, attached is a txt doc showing the series of numbers up to 1680. I have gone beyond this figure by skipping 1681 and it seems the regularity at which an overflow occurs is increasing (not surprising). At 10000+ I’m overflowing every other number. My gut feeling is the conjecture will hold but will need some serious number crunching to go beyond 1680. I will continue to look into this, maybe using some other means to verify the numbers that cause an overflow. Paul Cleary.