Collatz Breakthrough!

I am a bit late to the party on this, but last year saw a significant advancement in our general understanding of the Collatz Conjecture. Using methods similar to those used in solving partial differential equations, Terence Tao showed that the conjecture is true for almost all numbers. This goes beyond the work done by Ivan Korec by proving it for a larger population but falls short of proving it for all numbers. Admittedly, this proof probably will not be extended to all numbers, requiring a different methodology to progress even more.

A general description of the paper was recently published by Quanta Magazine.

Difference of squares - Part 2

In the first part, we introduced the problem, and proposed a solution, but found it inefficient at high numbers. Now we will try for a more efficient solution.

Solution #2

After digging around online a bit, it becomes obvious pretty quick that we can reduce our solution to a simple equation.

sumOfSquares n = n * (n+1) * (2*n+1) `div` 6
squareOfSum n = (n * (n+1) `div` 2) ^ 2

This simplifies it immensely, and we run out of ways to represent n before the calculation lags now.

But, what did we do here?

Proof

So we have found the formula of (n * (n+1) * (2n+1)) / 6 is equal to our sumOfSquares formula. Our testing has worked out, but we want to be sure that they are the same. So of course, let's prove it, and how else, but by induction.

Base case:

N = 1

(N * (N+1) * (2N + 1)) / 6 ==>
(1 * (1+1) * (2*1 +1)) / 6 ==>
6 / 6 = 1

That checks out. Now on to the next step.

Let's assume that for N = K the following statement is true:

1^2 + 2^2 + 3^2 ... K^2 = (K * (K+1) * (2K+1)) / 6

If that is true, then N = K+1 becomes:

1^2 + 2^2 + 3^2 ... (K+1)^2 = ((K+1) * ((K+1)+1) * (2(K+1)+1)) / 6 = ((K+1)*(K+2)*(2K+3))/6

This can be rewritten as:

1^2 + 2^2 + 3^2 ... K^2 + (K+1)^2 = (K * (K+1) * (2K+1)) / 6 + (K+1)^2

The right-hand side reduces down to:

((K+1)(2K^2 + 7K + 6)) / 6 ==> ((K+1)(K+2)(2K+3)) / 6

Since the left-hand side is equal to the right-hand side, we are done!

Background

It turns out that the above is a specific case of the more general idea of Bernoulli's Numbers, which is used in numerous other places including Fermat's Theorem and Euler-Maclaurin summation.

Wrapping Up

This post has already gone on for far too long (like anyone got this far). The analysis of the other formula used will have to wait for a future post. As will further exploration of Bernoulli and his numbers. 

Difference of squares - Part 1

This post was inspired by an exercise on Exercism and Project Euler. Be warned, I will be showing solutions that should work for both of those sites, so... if you don't want spoilers, leave now (and come back later when you have finished).

The Problem

The difference of squares problem is simply stated as determining the difference between the sum of squares and square of sums for a sequence of numbers from 1 to N.

An example:

The sum of squares for the first five natural numbers is:

(1^2 + 2^2 + 3^2 + 4^2 + 5^2) = 55

The square of sums for the first five natural numbers is:

(1+2+3+4+5)^2 = 225

With the difference between the two sequences being:

225 - 55 = 170

Solution #1

So the problem seems pretty easy, and in Haskell, it becomes almost trivial.

Let's take the first step as the sum of squares.

sumOfSquares :: Integral a => a -> a
sumOfSquares n = sum $ fmap (^2) [1..n]

We first generate a list of numbers from 1 to the input N. Then square each number in the sequence and sum the entire list. Simple

On to the square of sums.

squareOfSum :: Integral a => a -> a
squareOfSum n = (^2) $ sum [1..n]

Similarly here, we generate a list, but now sum it up, and the square the result.

The difference between the two hopefully is obvious:

difference :: Integral a => a -> a
difference n = squareOfSum n - sumOfSquares n

This solution is extremely trivial to implement, not only in Haskell but other languages as well. But, it is not exactly efficient. First, we are doing n+1 squares. Second, we are generating the same list multiple times. Even so, this performs pretty quickly on my machine up through ~ 1,000,000. After that, the operations start to slow down. 

But we can do better surely, and do so in the next post. 

Collatz Conjecture

The Collatz Conjecture, known by many other names, including 3n+1, and the Ulam Conjecture, is a problem, that while stated simply, has proven extremely difficult to solve.

The problem simply stated is, for any number n, if odd, multiple by three and add one, or, if even, divide by two, will the sequence converge on one?

Example: if you start with n = 10, then:

• 10 % 2 = 0
• n = 10 / 2 = 5

• 5 % 2 = 1 
• n = 3 * 5 + 1 = 16

• 16 % 2 = 0
• n = 16 / 2 = 8

• 8 % 2 = 0
• n = 8 / 2 = 4

• 4 % 2 = 0
• n = 4 / 2 = 2

• 2 % 2 = 0
• n = 2 / 2 = 1

• n = 1

Richard Guy lists it as one of the problems you should not try to solve, or at the very least, without first referencing the work that has been done to date. Namely, Eric Roosendaal's site appears to be the most current resource.

Below is sample code to print the sequence for any starting value of n:

def collatz(x):

...     while(x > 1):

...             if((x % 2) == 0):

...                     x = x / 2

...             else:

...                     x = (3 * x) + 1

...             print x

Ulam Sequence

Almost everyone is familiar with Fibonacci sequence. I remember first learning about this in high school math and science classes. Later, I would explore it more, albeit tangentially, in computer science as I coded it over and over again to demonstrate recursion and iteration. However, I only recently learned of a somewhat similar sequence, the Ulam sequence. Today I will explore the basics of this sequence and provide a simple (and very inefficient) program to calculate the sequence. Overall, I am intrigued by this topic, so it may become a recurring topic as I explore it more.

First, let's discuss what the Ulam Sequence is. The official definition is: "The Ulam sequence  is defined by , , with the general term  for  given by the least integer expressible uniquely as the sum of two distinct earlier terms." (Wolfram) What this means is that if you have a number greater than 2, it is a Ulam number if and only if, it is the unique sum of two other Ulam numbers.

The normal example is that the series starts with 1, 2, 3, 4, 6, 8, 11. 3 is the unique sum of 1 and 2. 4 is the unique sum of 3 and 1; while it is also the sum of 2 and 2, you can only use the same number once. 5 is not a Ulam number. It is the sum of 4 and 1 and 3 and 2. Once you get past these initial numbers, you can also ignore the sum of non-Ulam numbers in making the final determination. For example, 8 is the unique sum of 6 and 2. It is also the sum of 7 and 1, but since 7 is not a Ulam number, it does not invalidate 8. 

Additional resources and references:

In addition to the links above, Donald Knuth notes that a bitwise algorithm can be used to speed up the calculation of the series through 1,000,000. 

Richard Guy list several of the open questions regarding the series in his book Unsolved Problems in Number Theory.

And the Online Encyclopedia of Integer Sequences lists the currently known members of the series.

Finally, below is the simple program that I created while working through this. I make no claim to it being efficient, or even accurate, but it does match the listed sequence for U100 and below. It starts to bog down around 26,000. 

def ulam_count():

    i = 3400

    j = 3

    u = [1,2]

    while(j <= i):

        c = 0

        for a in u:

            for b in u:

                if( a >= b): 

                    pass

                elif((a + b) == j):

                    c = c + 1

                else:

                    pass

        if(c == 1):

            u.append(j)

        j = j +1

        u.sort()

   print(u)

ulam_count()

Introduction

Yet another blog on number theory? Better yet, yet another blog on number theory with no substance to it? Well... yes. This is mostly for my own amusement. I am in the process of acquainting myself with the topic. This is purely in the hobby realm. I am not a student. I am not a mathematician, and what little training I have had on the subject is many years old at this point, and mostly forgotten. I will be using a number of books supplemented by various websites to explore this topic. 

Where does that leave us? Well, that means that I will mostly be rehashing pretty elementary topics that you can probably find coverage on in any number of other places. It also means, that little of what I write here will be novel. And really, in the unlikely event that I come up with the latest proof of Fermat's Last Theorem... well I will post it here after it has been published elsewhere. 

So join me on this journey. A journey that promises to be wandering, mundane, and uninsightful.