Invariant Properties

This is a followup to an item in the last post. It’s all general pointers and nothing’s specific to any question.

Know your tools. Using a relational database on a home computer to hold billions of values in a OEIS sequence is probably not a good idea. My gut instinct is that you should be able to use 10k records in an in-memory database (e.g., h2) and up to 100k records in a ‘real’ database (e.g., oracle, sql server, postgresql or mysql). The in-memory estimate is probably too small since these are small records so you won’t chew up much memory. These aren’t hard limits, of course, but just my instinct of where you will start to need to pay attention to database issues beyond ‘how do I get to my data?’.

A second issue is how you store the data. Simple sequences are trivial to store. Collections, e.g., sets of amicable numbers, should be stored using a standard one-to-many approach instead of creating one row with a bunch of columns. It’s more work up front but much more useful later.

Don’t do individual inserts. An individual query may only take 1-2 ms but if you’re adding hundreds of thousands or even millions of records that time adds up. Every serious database allows you to do a bulk load from an external file, e.g., the “COPY” instruction in postgresql. Use it.

Be careful here. There are tools like dbunit that allow you to specify bulk data but as I recall it’s ultimately implemented as individual insert statements. You want to use your database’s tools, not a third party that might not be as efficient.

Use bulk load format compatable with Excel et al. Yes, you can read the file directly. But it’s a pain and you might miss what’s tripping up your database. E.g., are you properly escaping quotes?

In practice this means a tab- or comma-separated values (CSV) file. This is such a widely used format that it should be a safe bet for all databases.

Something to keep in mind is that there are file limitations. E.g., Excel files are limited to a bit over 65k records. Other databases may restrict the number of records in a bulk insert, or they may have a limitation on the total number of bytes. You may need to split your bulk inserts into multiple files.

Create solid file creation applications. By that I mean that the algorithms should be well-documented and self-validating. E.g., if you know that every third value should be even then you should verify that before writing the file. It’s a good way to document what you know in addition to being a Really Good Idea in general.

Capture what you learn. A lot of PE problems will create (or at least use) new OEIS sequences. Add them to your database.

Follow conventions. This is easy – if your data is something with an OEIS sequence then make sure your sequence matches. This is mostly knowing what value to start with, e.g., starting at index 2.

Finally, don’t be afraid to use external resources. You definitely want to do the PE problem first. Sometimes there’s only a few more values, e.g., the list of perfect numbers, and it makes sense to just list them explicitly after you’ve finished the PE problem. You never know when you’ll need those values later.

Project Euler (http://projecteuler.net/) is an interesting site for somebody who wants to develop their mathematical skills or keep them sharp. It’s really cool that (at the introductory level) there’s usually a brute force approach in a classic procedural language like Java, a cleaner brute force approach in a functional language, and a much cleaner solution if you use a bit of math. You can learn a lot by exploring the last approach.

There’s one problem though – there’s not enough information to know what to search for if you don’t already know what to search for. You can get that information in the comments from others once you solve the problem via brute force methods but that requires you to solve the problem via brute force solutions. That’s not always practical.

Google is another approach but the links often give you the answer without providing insight into how to get there. That’s great if you only want to answer the question, not so great if you want to learn a bit more math.

Some sites provide a bit more insight into the problem. I’ll try to add my own feeble contributions. There will be a brief insight above the break and a fuller discussion below the break. Unfortunately this won’t help much if you’re reading an RSS feed. Sorry.

The first issue is Fibonacci sequences.  That is, slightly rephrased from the Project Euler definition, the sequence defined by:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) where n > 1

(The other common definition sets the first two values to 1 but the results are equivalent.)

So what insight do we have regarding the sum of even terms?…

Think back to elementary school math.  We  all learned a very simple rule:

• the sum of two even numbers is even.
• the sum of an even and odd number is odd.
• the sum of two odd numbers is even.

This means that a sequence of sums like the Fibonacci can have only two possible forms:

• all even numbers
• one even number, two odd numbers, one even number, repeat….

If follows that a sum of even Fibonacci terms will only need to consider every third value.

Continue reading this entry »