Re:Sequence and first differences together list all positive...
by kleiba on Sunday June 29, 2025 @07:15AM
(#44412161)
Coding 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.
[ Parent
| on HN ]
Re:Sequence and first differences together list all positive...
by rokob on Sunday June 29, 2025 @09:03AM
(#44412807)
return n >= 0
Re:Sequence and first differences together list all positive...
by r0uv3n on Sunday June 29, 2025 @09:17AM
(#44412914)
2 for example is not in the sequence. Remember that you need the first differences to this sequence to obtain all natural numbers
Re:Sequence and first differences together list all positive...
by rokob on Sunday June 29, 2025 @10:07AM
(#44413284)
Hah oh right duh
Re:Sequence and first differences together list all positive...
by vbezhenar on Sunday June 29, 2025 @09:15AM
(#44412903)
Compute the sequence until you get n or m > n?
Re:Sequence and first differences together list all positive...
by haskellshill on Sunday June 29, 2025 @09:51AM
(#44413159)
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.
Re:Sequence and first differences together list all positive...
by sltkr on Sunday June 29, 2025 @11:34AM
(#44413924)
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)