Partitions and OEIS: On-Line Encyclopedia of Integer Sequences

 For this term I decided to take a non-credit lesson called Experimental Mathematics and in this course I've found out about an amazing tool called OEIS. OEIS stands for On-Line Encyclopedia of Integer Sequences. 

Basically it's an extensive list of interesting sequences. If you come across any sequence in your studies, you don't have to hit your head against a wall hoping to figure out the pattern. You just go to here and type it. If there exists a pattern in that sequence this site will probably tell you. For any sequence you type, you can find previous work done on that sequence.

I cannot express how excited I am to have met this tool. A big part of my time this week was spent trying to find new patterns or looking up already existing sequences and reading about their other properties.

Here are some interesting sequences:

    1, 101, 1001, 10001, 100001, 112233, 10000001, 100122, 1000011...

Can you see the pattern? If not, worry not, just type it into OEIS.

This is the sequence of smallest number whose digits can be permuted to get exactly n distinct palindromes.

    1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 3, 0, 2, 0, 2, 1, 1, 0, 4, 1, 1, 1, 2, 0, 3, 0, 3, 1, 1, 1, 5, 0, 1, 1, 4...

Does this even have a pattern? Well yes it does, it is the number of even length factorizations of n into factors greater than one.

    7, 13, 19, 23, 31, 79, 97, 103, 109, 139, 167, 193, 239

Well these are clearly prime but what kind of prime? They are happy :) primes!  Happy prime is a prime that eventually reaches 1 under iteration of "x -> sum of squares of digits of x".

You get the point. This is an extremely strong tool for those who like to mess around with numbers. The thing I messed around with most this week was partitions.

Integer Partitions

 Partition is a collection of ways to sum positive numbers to get n. For example the partitions of 4 are:

4=4    4=3+1    4=2+2    4=2+1+1    4=1+1+1+1

Can you think of a function that gives the numbers of partitions of n? Here are the first 15 integers:

My initial instinct to approach this problem was incorrect. I had thought that 

$f_1$(n)=[ $f_1$(n-1) $f_1$(1) + $f_1$(n-2) $f_1$(2) +...+ $f_1$(1) $f_1$(n-1) ] / 2

This idea stemmed from the fact that a partition consisted of smaller partitions. But as you can clearly see you were counting some partitions way too many times. Plus, sometimes in even numbers you would get non-integer results.

During the lesson, we learned how to approach this kinda problem. If you are curious you can check it out here. But my mind got stuck on a question "Can I just substract some function from $f_1$ in order to get the result I want?" How many times am I counting the extra partitions? I changed the function a bit in order fix the even/odd problem. Then, I looked at the difference between the actual numbers of partitions vs $f_1$:

 It looked proportional to the true partition function. So maybe I could get an answer from here. $f_1$'s result were:

[1, 2, 7, 11, 26, 40, 83, 120, 223, 320, 566, 784, 1310, 1802, 2922]

while the true results were:

[2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176]

 I've searched OEIS for "1, 2, 7, 11, 26, 40, 83, 120, 223, 320, 566" but unfortunately there wasn't a previously worked on pattern. 

Then what happened was me trying many different ways to calculate what to substract. In the end I failed. I couldn't find a proper function to substract. Well that's just mathematics, you can't solve everything yourself. Maybe I'll be able to solve it in a few years, maybe not. 

If you have any idea on how to solve this problem please mail me. I would be extremely happy.