Let T(N) be the number of distinct (non-congruent) triangles with integer sides and perimeter N.  For example, T(12) = 3 because there are three distinct triangles with integer sides and perimeter 12. There’s the equilateral triangle with sides 4 : 4 : 4, and the Pythagorean triangle 3 : 4 : 5. With a little more work we can find 2 : 5 : 5.

The authors in [1] developed an algorithm for finding T(N). The following Python code is a direct implementation of that algorithm.

    def T(N :int):
        if N < 3:
            return 0
        base_cases = {4:0, 6:1, 8:1, 10:2, 12:3, 14:4}
        if N in base_cases:
            return base_cases[N]
        if N % 2 == 0:
            R = N % 12
            if R < 4:
                R += 12
            return (N**2 - R**2)//48 + T(R)
        if N % 2 == 1:
            return T(N+3)

If you’re running a version of Python that doesn’t support type hinting, just delete the :int in the function signature.

Since this is a recursive algorithm, we should convince ourselves that it terminates. In the branch for even N, the number R is an even number between 4 and 14 inclusive, and so it’s in the base_cases dictionary.

In the odd branch, we recurse on N+3, which is a little unusual since typically recursive functions decrease their argument. But since N is odd, N+3 is even, and we’ve already shown that the even branch terminates.

The code (N**2 - R**2)//48 raises a couple questions. Is the numerator divisible by 48? And if so, why specify integer division (//) rather than simply division (/)?

First, the numerator is indeed divisible by 48. N is congruent to R mod 12 by construction, and so N – M is divisible by 12. Furthermore,

N² – R² = (N – R)(N + R).

The first term on the right is divisible by 12, so if the second term is divisible by 4, the product is divisible by 48.  Since N and R are congruent mod 12, N + R is congruent to 2R mod 12, and since R is even, 2R is a multiple of 4 mod 12. That makes it a multiple of 4 since 12 is a multiple of 4.

So if (N² – R²)/48 is an integer, why did I write Python code that implies that I’m taking the integer part of the result? Because otherwise the code would sometimes return a floating point value. For example, T(13) would return 5.0 rather than 5.

Here’s a plot of T(N).

[1] J. H. Jordan, Ray Walch and R. J. Wisner. Triangles with Integer Sides. The American Mathematical Monthly, Vol. 86, No. 8 (Oct., 1979), pp. 686-689

The previous post looked at random Fibonacci sequences. These are defined by

f₁ = f₂ = 1,

and

f_n = f_n-1 ± f_n-2

for n > 2, where the sign is chosen randomly to be +1 or -1.

Conjecture: Every integer can appear in a random Fibonacci sequence.

Here’s why I believe this might be true. The values in a random Fibonacci sequence of length n are bound between –F_n-3 and F_n.[1] This range grows like O(φⁿ) where φ is the golden ratio. But the number of ways to pick + and – signs in a random Fibonacci equals 2ⁿ.

By the pigeon hole principle, some choices of signs must lead to the same numbers: if you put 2ⁿ balls in φⁿ boxes, some boxes get more than one ball since φ < 2. That’s not quite rigorous since the range is  O(φⁿ) rather than exactly φⁿ, but that’s the idea. The graph included in the previous post shows multiple examples where different random Fibonacci sequences overlap.

Now the pigeon hole principle doesn’t show that the conjecture is true, but it suggests that there could be enough different sequences that it might be true. The fact that the ratio of balls to boxes grows exponentially doesn’t hurt either.

Empirically, it appears that as you look at longer and longer random Fibonacci sequences, gaps in the range are filled in.

The following graphs consider all random Fibonacci sequences of length n, plotting the smallest positive integer and the largest negative integer not in the range. For the negative integers, we take the absolute value. Both plots are on a log scale.

First positive number missing:

Absolute value of first negative number missing:

The span between the largest and smallest possible random Fibonacci sequence value is growing exponentially with n, and the range of consecutive numbers in the range is apparently also growing exponentially with n.

The following Python code was used to explore the gaps.

    import numpy as np
    from itertools import product

    def random_fib_range(N):
        r = set()
        x = np.ones(N, dtype=int)
        for signs in product((-1,1), repeat=(N-2)):
            for i in range(2, N):
                b = signs[i-2]
                x[i] = x[i-1] + b*x[i-2]
                r.add(x[i])
        return sorted(list(r)) 

    def stats(r):
        zero_location = r.index(0)

        # r is sorted, so these are the min and max values
        neg_gap = r[0]  // minimum
        pos_gap = r[-1] // maximum
     
        for i in range(zero_location-1, -1, -1):
            if r[i] != r[i+1] - 1:
                neg_gap = r[i+1] - 1
                break
        
        for i in range(zero_location+1, len(r)):
            if r[i] != r[i-1] + 1:
                pos_gap = r[i-1] + 1
                break
        
        return  (neg_gap, pos_gap)

    for N in range(5,25):
        r = random_fib_range(N)
        print(N, stats(r))

Proof

Update: Nathan Hannon gives a simple proof of the conjecture by induction in the comments.

You can create the series (1, 2) and (1, 3). Now assume you can create (1, n). Then you can create (1, n+2) via (1, n, n+1, 1, n+2). So you can create any positive even number starting from (1, 2) and any odd positive number from (1, 3).

You can do something analogous for negative numbers via (1, n, n-1, -1, n-2, n-3, -1, 2-n, 3-n, 1, n-2).

This proof can be used to create an upper bound on the time required to hit a given integer, and a lower bound on the probability of hitting a given integer during a random Fibonacci sequence.

Nathan’s construction requires more steps to produce new negative numbers, but that is consistent with the range of random Fibonacci sequences being wider on the positive side, [-F_n-3, F_n].

***

[1] To minimize the random Fibonacci sequence, you can chose the signs so that the values are 1, 1, 0, -1, -1, -2, -3, -5, … Note that absolute value of this sequence is the ordinary Fibonacci sequence with 3 extra terms spliced in. That’s why the lower bound is –F_n-3.