[HN Gopher] Sequence and first differences together list all pos...
___________________________________________________________________
Sequence and first differences together list all positive numbers
exactly once
Author : andersource
Score : 71 points
Date : 2025-06-25 08:59 UTC (4 days ago)
(HTM) web link (oeis.org)
(TXT) w3m dump (oeis.org)
| 8organicbits wrote:
| OEIS 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 wrote:
| For 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)
| volemo wrote:
| > A true shame that he went insane
|
| Could you elaborate on your reasons for calling Eric
| Weisstein insane?
| Rexxar wrote:
| He 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 wrote:
| Weisstein is amazing. Wolfram has the "unified theory of
| everything" disease. So much so that he sponsored dozens of
| youtube channels to talk about it.
| foodevl wrote:
| I 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 wrote:
| More likely he's confusing the mathworld author with
| Stephen Wolfram
| lutusp wrote:
| > 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.
| HocusLocus wrote:
| Like 'even and odd' on steroids.
| kleiba wrote:
| Coding exercise: write a function boolean
| isInSequence(n):
|
| 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.
| rokob wrote:
| return n >= 0
| r0uv3n wrote:
| 2 for example is not in the sequence. Remember that you need
| the first differences to this sequence to obtain all natural
| numbers
| rokob wrote:
| Hah oh right duh
| vbezhenar wrote:
| Compute the sequence until you get n or m > n?
| haskellshill wrote:
| How about the following Haskell program? rec
| ((x:xs),p) = (filter (/= p+x) xs,p+x) sequ = map snd $
| iterate rec ([2..],1)
|
| sequ is an infinite list of terms of the sequence A005228.
| sltkr wrote:
| That 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)
| asboans wrote:
| I don't know but I think I could probably implement
| IsInSequenceOrFirstDifferences(n)
| cluckindan wrote:
| Recursive (n choose 2) is my favorite.
|
| https://oeis.org/A086714
|
| 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.
| OscarCunningham wrote:
| Is there a sequence where the sequence and all its differences
| contain each positive integer once?
|
| Something like 1 3 9 26 66 2 6 17
| 40 4 11 23 7 12 5
|
| Oh, here it is: https://oeis.org/A035313
| thaumasiotes wrote:
| > 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.
| vishnugupta wrote:
| Can someone please explain this to me? I tried to make sense but
| couldn't.
| Horffupolde wrote:
| The sequence union the differences span all integer values.
| munchler wrote:
| The 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 wrote:
| Really good explainer. Thank you!
| card_zero wrote:
| By 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.
| Aardwolf wrote:
| I 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
___________________________________________________________________
(page generated 2025-06-29 23:01 UTC)