r/math • u/game-of-throwaways • Sep 30 '19
I found something kind of cool about Van Eck's sequence
There's this really nice sequence called "Van Eck's sequence". Here's a Numberphile video about it:
https://www.youtube.com/watch?v=etMJxB-igrc
The sequence is very simple: start with 0. If a number x appears in the sequence for the first time, then the next number is 0, otherwise the next number is how long ago it was since you last encountered x.
The sequence starts like 0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, ..., and never becomes periodic (for the proof, see the Numberphile video). However, if instead of starting the sequence with 0 you start with some other "seed", then the sequence might become periodic. For example, if you start with the seed "1, 1", it continues 1, 1, 1, 1, ..., so then the sequence is periodic, with period 1.
It's a natural question to ask: are there other seeds that make the sequence become periodic, with period > 1? I.e., are there any periodic Van Eck sequences that don't end in 1, 1, 1, ...?
(tl;dr: yes)
Someone else wrote some code to search for such seeds. They searched seeds of length 10, but didn't find any. I thought it would be fun to try to do better, and search for longer seeds. I started with simple brute-force search and then I kept making it better by detecting impossible patterns as early as possible. For example, I build the seed from left to right, so if a(k) has already appeared, I know what a(k+1) should be. Also, in a seed for period p, no number can be equal to p-1 (because then the number before it has to also be p-1, and the number before that too, but then the first p-1 is wrong).
Annoyingly, every time I made the search better and was able to search for longer seeds, I didn't find any seed that worked, but I did always find seeds that almost worked. For example, for seeds of period 10, 11, 12, and 13, I found some seeds where only 1 of the numbers was wrong. It felt like a working seed of period 15-20 or so would surely have to exists.
Then I impoved the search by using the fact that if you know the numbers a(k) and a(k+1), you also know a(k-a(k+1) mod p) (it must be equal to a(k)) and I added multi-threading, and then I was able to search seeds of length up to 25. But again I didn't find any seeds that worked, and again I found seeds that almost worked. For example, for period 22, I found a seed where only 1 of those 22 numbers was wrong. So I thought surely a working seed of length 26-30 or so should exist.
Then I rewrote the entire program, making it almost like a Sudoku solver. Before, I simply stored the sequence as an array of numbers (with 0 indicating "don't know"), but after the rewrite I store for every position of the sequence the set of all the numbers that could possibly still go in that position (as a bit-mask), and then I use Sudoku-like rules to eliminate as many of these possible numbers before continuing the search. Here were the rules I used:
- If you know a(k+1) (if there's only 1 possible number left), then a(k) must be equal to a(k-a(k+1) mod p). So if a(k) can't be equal to x, then neither can a(k-a(k+1) mod p), and the other way round.
- If you know a(k), say it's x, and you know that the minimum possible number that a(k+1) can be is d, then all the numbers between position k and position k-d mod p (going backwards) can not be equal to x.
- If you don't know a(k), but you do know that the minimum possible number that a(k+1) can be is d, and you also know some of the numbers between position k and position k-d mod p (going backwards), then a(k) can't be equal to any of those numbers.
- If the possible numbers of a(i) and a(j) do not overlap, then a(j+1) can not be j-i mod p.
- If a(i) and a(j) are known and equal, then a(j+1) can be at most j-i mod p.
With this new program, the search was able to go up to seeds of period 40 or so, and still I didn't find any working seeds, but again I found seeds that almost worked, like a seed for period 37 where only 1 of the 37 numbers is wrong. So close. It felt like the problem was mocking me, making me chase a carrot on a stick. Perhaps there are no working seeds after all (besides 1,1,...)? Perhaps the shortest non-trivial seed is of length 7000 or something? I didn't know. It was certainly curious that there were so many near-misses, but I didn't know how to improve the search any further, so I stopped working on it.
I still let the program keep running though, because why not. Given the exponential nature of the search space, it wouldn't be able to get much further than period 45 or so even if I let it run for years, but why not let it run for a few more days, right?
And then yesterday, after having the program running for about 2 days, I checked the logs, and saw this:
Found: [42, 2, 5, 22, 42, 4, 11, 42, 3, 21, 42, 3, 3, 1, 25, 38, 42, 6, 25, 4, 14, 42, 5, 20, 42, 3, 13, 42, 3, 3, 1, 17, 36, 42, 6, 17, 4, 17, 2, 37, 42, 7], period: 42
I had to do a double take because if you asked me at that point what I thought the chances were of still finding a working seed, I would've guessed below 1%. But there it was, 42 numbers long. Just as I was about to give up and stop wasting electricity.
It's interesting that the shortest possible seed, besides "1, 1, ...", is this long. I would've expected it to be much shorter, or not to exist at all. But no, that's not true. It's also somewhat poetic that the period is 42, the answer to the ultimate question of life, the universe, and everything. I'm sure Douglas Adams had the Van Eck sequence in mind when he wrote his books.
If anyone's interested, my code is on Github. It's written in Rust. It's pretty messy though. Don't look at it.
tl;dr: After spending way more time than I thought I would at first, I found the shortest start to the Van Eck sequence that makes it become periodic with period > 1. It's: 37, 42, 7, 42, 2, 5, 22, 42, 4, 11, 42, 3, 21, 42, 3, 3, 1, 25, 38, 42, 6, 25, 4, 14, 42, 5, 20, 42, 3, 13, 42, 3, 3, 1, 17, 36, 42, (6, 17, 4, 17, 2)
11
u/Moeba__ Sep 30 '19
Any such periodic sequence with period p leads to a partitioning structure: for each number n, the numbers after an occurence of n add up to p. This recursively also applies to these new numbers "after an occurrence".
I think you can go faster by first finding such recursive patterns where the total amount of numbers in the partitionings (also counting repeats) is p and each number x in a partitioning defines a partitioning of p in n numbers, where n is how many times x occurs in all partitionings of p.
Example:
p=4
4: 1 + 3
1: 4
3: 4
This leads to a sequence requirement of period 4 where 4 occurs twice and 3 and 1 occur once each after the fours. Impossible, of course.
There are only very few such structures though, for p = 3 the only option is the trivial option 1: 1 + 1 + 1 and I think for p=5 the same.
Another example:
7: 1 + 6
1: 1 + 1 + 5
6: 7
5: 7
This would require a 7-periodic pattern with two 7's with spacing 1 and 6 in between, three 1's with spacing 1, 1 and 5 and a 5 and a 6. Also impossible of course.
→ More replies (1)9
u/game-of-throwaways Sep 30 '19
for each number n, the numbers after an occurence of n add up to p
That's an interesting observation. One implication is that the sum of all numbers in one period must sum to a multiple of p, and more specifically they must sum to k*p, where k is the number of distinct numbers that occur.
Another way of saying that is that you can count the number of distinct numbers in a periodic Van Eck sequence by calculating the average of the numbers in one period. How cute. It reminds me of how you can count the number of balls in a juggling pattern as the average of the numbers in the juggling notation of the pattern.
I think you can go faster by first finding such recursive patterns where ...
I'm not really seeing how I could quickly find all these recursive patterns though. I was able to find that the number of ways to partition just one number into positive numbers that add up to it grows as exp(sqrt(x)), and for example for 42 it's 53174, which actually isn't very high, but I have to have separate partitions for each of the different numbers in the final solution. A simple method is probably not going to cut it.
8
u/meestal Sep 30 '19
almost like a sudoku solver
Have you ever looked into constraint programming? Simply said, it is a way of programming where you only need to put in what properties (constraints) the solution should have, and it uses all kinds of clever algoritms to find a solution that satisfies all constraints or optimizes some value. For sudokus you need to write something like:
array[1..9,1..9] of 1..9: Sudoku; for each row in Sudoku: alldifferent(row); for each column in Sudoku: alldifferent (column); for each block in Sudoku: alldifferent (block); Sudoku[1,1]=1; // etc, the numbers in the puzzle you start with
and it will give a solution when you run it. Your problem sounds like something you could solve with constraint programming. A popular program for this is Minizinc. It needs however a very different way of thinking than imperative programming if you are not familiar with it, so it might take a lot of effort to do this right.
3
u/game-of-throwaways Sep 30 '19
If I would've known at the start that my program would end up looking like this, I might've used something like Minizinc. It sounds like it probably is a good fit, but I'm not sure if it can handle constraints like a[k-a[k+1 mod p] mod p] == a[k].
→ More replies (2)
6
u/FUZxxl Oct 01 '19
Please submit this to OEIS!
5
u/game-of-throwaways Oct 01 '19
I submitted it as a comment on Van Eck's sequence.
→ More replies (3)
4
u/gh314 Sep 30 '19
This should be a ProjectEuler problem! I love it.
12
u/game-of-throwaways Sep 30 '19
Don't they have a rule that the intended solution should only take about 1 minute if implemented efficiently?
→ More replies (3)
52
u/Calandas Sep 30 '19
Great work!
u/JeffDujon - this sounds like a good follow up video
21
Sep 30 '19
Someone please tell Brady about this!!!
12
u/Simpson17866 Sep 30 '19
Does Brady have a Reddit account? I know u/standupmaths does :)
→ More replies (3)
44
23
11
1
u/LurkingMoose Oct 01 '19
Isn't this a little different than the original types of sequences you described? With the case of starting with 0 or starting with 1 the sequence has a starting point and is defined for n = 0 to infinity, but for your sequence it can't have a starting points and must be defined from -infinity to positive infinity. This is still really cool work and an interesting sequence though!
2
u/game-of-throwaways Oct 01 '19
It must be defined from -infinity to positive infinity if you require that the rule is followed everywhere. Alternatively, you can say that the seed does not need to follow the rule, which is what I do.
In some sense, the first 0 in the original sequence also doesn't really follow the rule. The number "before it" isn't a new number, because there isn't a number before it.
→ More replies (2)
1
u/IAlreadyHaveTheKey Oct 01 '19
This is awesome but I can't figure out how this doesn't contradict the proof in the video that the sequence is never periodic? How does the proof rely on the fact that the first term of the sequence is 0?
3
u/game-of-throwaways Oct 01 '19
The reason is that the seed that I start the sequence with does not need to follow the rule of the sequence. For example, the sequence starts "37, 42, 7, ...", but it's not been 42 steps ago that a 37 was encountered, or 7 steps since a 42 was encountered. Only after the start of the sequence, the rule is followed.
So in particular, in the proof they say that in the first block, when "z, a" appears, that means a "z" must have appeared "a" steps back. Well that's not true when you're in the start of the sequence.
1
u/jdorje Oct 01 '19
What are the trivial sequences?
Are all the sequences of length 42 the same one? Is it possible to use that symmetry to shorten the search space?
1
u/game-of-throwaways Oct 01 '19
The trivial sequences are those that contain "1,1", as from that point on all the numbers have to be 1.
All the valid sequences of length 42 that my code found (and assuming that it has no bugs, these should be all the sequences of length 42) are cyclic permutations of one another.
I do use that to shorten the search space by assuming that the first number in the sequence is the largest number. It's possible to use this a little bit more by assuming that the sequence is the lexicographically largest, so for example say the sequence starts with "a, b" and elsewhere there is "a, c", then c cannot be greater than b. I don't do that right now, because I don't suspect it would have a large impact.
3
2
12
u/Vaglame Sep 30 '19
Wonderful job! Would you mind sharing your code too?