Sequence and first differences together list all positive numbers exactly once
81 points by andersource 2 weeks ago | 29 comments- OscarCunningham 2 weeks agoIs there a sequence where the sequence and all its differences contain each positive integer once?
Something like
Oh, here it is: https://oeis.org/A0353131 3 9 26 66 2 6 17 40 4 11 23 7 12 5- thaumasiotes 2 weeks ago> Oh, here it is: https://oeis.org/A035313
That sequence is not known to match what you asked for:
>> Conjecturally, every positive integer occurs in the sequence or one of its n-th differences, which would imply that the sequence and its n-th differences partition the positive integers.
For an intuition of why this might be hard to prove, note that you had to insert 7 into your structure before you inserted 5. In the general case, there might be a long waiting period before you're able to place some particular integer n. It might be infinitely long.
- 2 weeks ago
- thaumasiotes 2 weeks ago
- 8organicbits 2 weeks agoOEIS is such a wonderful reference. I've had occasions where software I was building needed to compute certain sequences, but I hadn't yet figured out the underlying math. I popped the sequence into OEIS and found the closed form solution. It was a huge productivity boost.
- nurettin 2 weeks agoFor me it was a favorite place to visit every so often. I also really enjoyed mathworld.wolfram.com a few decades ago. (A true shame that he went insane)
- foodevl 2 weeks agoI don't know (and don't need you to elaborate on) exactly what you're referring to in that last sentence, but I suspect you are confusing Eric W. Weisstein with Eric Weisstein.
- quietbritishjim 2 weeks agoMore likely he's confusing the mathworld author with Stephen Wolfram
- quietbritishjim 2 weeks ago
- volemo 2 weeks ago> A true shame that he went insane
Could you elaborate on your reasons for calling Eric Weisstein insane?
- nurettin 2 weeks agoWeisstein is amazing. Wolfram has the "unified theory of everything" disease. So much so that he sponsored dozens of youtube channels to talk about it.
- Rexxar 2 weeks agoHe probably intends to call Stephen Wolfram like that. But it's ridiculous to call him insane because he seems a little obsessed by cellular automatons.
- nurettin 2 weeks ago
- lutusp 2 weeks ago> A true shame that he went insane
I assume you're referring to Stephen Wolfram, not Neil Sloane, but it seems many people would like clarification.
As to Wolfram, assuming this is your focus, nothing undermines one's sanity as reliably as complete success. Not to accept your premise, only to explain it.
- foodevl 2 weeks ago
- nurettin 2 weeks ago
- kleiba 2 weeks agoCoding exercise: write a function
that decides whether the given integer is part of that sequence or not. However, pre-storing the sequence and only performing a lookup is not allowed.boolean isInSequence(n):- asboans 2 weeks agoI don’t know but I think I could probably implement IsInSequenceOrFirstDifferences(n)
- haskellshill 2 weeks agoHow about the following Haskell program?
sequ is an infinite list of terms of the sequence A005228.rec ((x:xs),p) = (filter (/= p+x) xs,p+x) sequ = map snd $ iterate rec ([2..],1)- sltkr 2 weeks agoThat just enumerates the entire sequence; I think the challenge is to do it faster than that.
By the way, the use of `filter` makes your implementation unnecessarily slow. (The posted link also contains Haskell code, which uses `delete` from Data.List instead of `filter`, which is only slightly better.)
I'd solve it like this, which generates both sequences in O(n) time, and the mutual recursion is cute:
a005228 = 1 : zipWith (+) a005228 a030124 a030124 = go 1 a005228 where go x ys | x < head ys = x : go (x + 1) ys | otherwise = x + 1 : go (x + 2) (tail ys)
- sltkr 2 weeks ago
- vbezhenar 2 weeks agoCompute the sequence until you get n or m > n?
- rokob 2 weeks agoreturn n >= 0
- asboans 2 weeks ago
- cluckindan 2 weeks agoRecursive (n choose 2) is my favorite.
If you think about it, it quantifies emergence of harmonic interference in the superposition of 4 distinct waveforms. If those waveforms happen to have irrational wavelengths (wrt. each other), their combination will never be in the same state twice.
This obviously has implications for pseudorandomness, etc.
- vishnugupta 2 weeks agoCan someone please explain this to me? I tried to make sense but couldn’t.
- munchler 2 weeks agoThe initial sequence is 1, 3, 7, 12, 18, 26, 35, etc. The difference between each term in that sequence produces a second sequence: 2, 4, 5, 6, 8, 9, 10, etc. If you merge those two sequences together in sorted order, you get 1, 2, 3, 4, 5, 6, 7, etc. Each whole number appears in the result exactly once.
- vishnugupta 2 weeks agoReally good explainer. Thank you!
- card_zero 2 weeks agoBy end of the sequence shown on the page, the contiguous part has only reached 61. After that it's full of gaps: it's hit 1689, but has not yet hit 62. The last three differences shown there are 59, 60, 61. So it will list all integers mainly because the differences are increasing similar to the ordinary number line.
- card_zero 2 weeks ago
- vishnugupta 2 weeks ago
- Horffupolde 2 weeks agoThe sequence union the differences span all integer values.
- munchler 2 weeks ago
- HocusLocus 2 weeks agoLike 'even and odd' on steroids.
- Aardwolf 2 weeks agoI wonder why the title of the sequence isn't set to "Hofstadter's sequence" since that seems to be what it's called according to A030124 when it refers back to this one
- andersource 1 week agoHofstadter introduces several sequences in GEB, [0] may be an interesting submission on its own but I was especially captivated by this self-referencing one. Plus a title including both Hofstadter's sequence and a description is too long for HN and I preferred the descriptive one
- Aardwolf 1 week agoI meant the title as it appears in OEIS, not as it appears on HN :)
- andersource 1 week agoAh :)
From my (limited) experience the OEIS titles lean strongly to the descriptive side too. But maybe also to avoid ambiguity regarding to which one is it from his sequences?
- andersource 1 week ago
- Aardwolf 1 week ago
- andersource 1 week ago