Link to video: www.youtube.com/watch?v=etMJxB-igrc
Link to the sequence on the On-Line Encyclopedia of Integer Sequences: https://oeis.org/A181391
It is a fairly simple to produce sequence: Starting at 0, determine if the number you last wrote exists in the sequence before that. If it does, write down the number of steps it is away from the last number you wrote; if it doesn't write down a 0. That's it.
I thought this would make quite a nice candidate for a spot of code golf, so I explained the problem to a friend and challenged him.
The things to consider in golf are:
- How many steps it takes to complete (once assembled, not steps in the high level language)
- How large the executable is (how cool your compiler is)
- How much RAM the program uses (not too many arrays, I hope)
- How few lines of code you can do it in (style points)
The OEIS does not include an example for doing it in C; I thought this a travesty, after all, it is one of the best languages, if not the best. So I decided to write my program using it. You may find my code below.
I initially wanted to use an array of chars whose indices represented the number in the sequence and whether it existed or not, but the problem with that is that you cannot search it (as fast as you might like), surprising problem to have I know. I wanted to test if a number existed in the sequence like this:
if(existingNumbers[index])
but that accesses the property directly. For some cases, that is great. But not here. For as soon as you set the current term, does it exist in the sequence. So when you go to check if it "already" exists in the sequence, this approach will always return true. So you have to search manually, which makes the program execute in O(n^2) time at worst. It's not quite that bad though.
#define NUM_TERMS 100
// ...
char sequence[NUM_TERMS];
memset(sequence, 0, NUM_TERMS);
for(char i = 1; i < NUM_TERMS; i++)
{
char index = i - 1;
char val = sequence[index];
for(char j = index - 1; j > -1; j--)
{
if(sequence[j] == val)
{
sequence[i] = index - j;
break;
}
}
}
I haven't seen my friend's code yet. I suspect he will do it in Java. I wonder if he'll let me share it here.
What's quite nice about this sequence is that each term gives you an idea of how long it took to generate. 0 = the worst case, it had to go to the start (so early zeroes aren't so bad, but later ones are), then as the magnitude of the number increases from 1, the longer it took to generate. Here are the first 100 terms:
00 00 01 00 02 00 02 02 01 06
00 05 00 02 06 05 04 00 05 03
00 03 02 09 00 04 09 03 06 14
00 06 03 05 15 00 05 03 05 02
17 00 06 11 00 03 08 00 03 03
01 42 00 05 15 20 00 04 32 00
03 11 18 00 04 07 00 03 07 03
02 31 00 06 31 03 06 03 02 08
33 00 09 56 00 03 08 07 19 00
05 37 00 03 08 08 01 46 00 06
There are some patterns in it, but they don't seem consistent. The encyclopedia looks into it deeper than I do.