Jacobsthal numbers: Difference between revisions
→{{header|Python}}: Added a variant defined in terms of a general unfoldr anamorphism
(→{{header|Haskell}}: Added a variant defined in terms of unfoldr) |
(→{{header|Python}}: Added a variant defined in terms of a general unfoldr anamorphism) |
||
Line 1,285:
{{out}}
<pre>First 30 Jacobsthal numbers:
0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763 349525 699051 1398101 2796203 5592405 11184811 22369621 44739243 89478485 178956971
Line 1,305 ⟶ 1,304:
174763
2796203
715827883</pre>
Or, defined in terms of a general unfoldr anamorphism:
<lang python>'''Jacobsthal numbers'''
from itertools import islice
from operator import mul
# jacobsthal :: [Integer]
def jacobsthal():
'''Infinite sequence of terms of OEIS A001045
'''
return jacobsthalish(0, 1)
# jacobsthalish :: (Int, Int) -> [Int]
def jacobsthalish(a, b):
'''Infinite sequence of jacobsthal-type series
beginning with a, b
'''
def go(xs):
a, *t = xs
return a, t + [2 * a + t[0]]
return unfoldr(go)([a, b])
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''First 15 terms each n-step Fibonacci(n) series
where n is drawn from [2..8]
'''
print('\n\n'.join([
fShow(k, n, xs) for (k, n, xs) in [
(
'terms of the Jacobsthal sequence',
30, jacobsthal()),
(
'Jacobsthal-Lucas numbers',
30, jacobsthalish(2, 1)
),
(
'Jacobsthal oblong numbers',
20, map(
mul, jacobsthal(),
drop(1)(jacobsthal())
)
),
(
'primes in the Jacobsthal sequence',
10, filter(isPrime, jacobsthal())
)
]
]))
# fShow :: (String, Int, [Integer]) -> String
def fShow(k, n, xs):
'''N tabulated terms of XS, prefixed by the label K
'''
return f'{n} {k}:\n' + spacedTable(
list(chunksOf(5)(
[str(t) for t in take(n)(xs)]
))
)
# ----------------------- GENERIC ------------------------
# drop :: Int -> [a] -> [a]
# drop :: Int -> String -> String
def drop(n):
'''The sublist of xs beginning at
(zero-based) index n.
'''
def go(xs):
if isinstance(xs, (list, tuple, str)):
return xs[n:]
else:
take(n)(xs)
return xs
return go
# isPrime :: Int -> Bool
def isPrime(n):
'''True if n is prime.'''
if n in (2, 3):
return True
if 2 > n or 0 == n % 2:
return False
if 9 > n:
return True
if 0 == n % 3:
return False
def p(x):
return 0 == n % x or 0 == n % (2 + x)
return not any(map(p, range(5, 1 + int(n ** 0.5), 6)))
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs.
'''
def go(xs):
return (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
return go
# unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
def unfoldr(f):
'''Generic anamorphism.
A lazy (generator) list unfolded from a seed value by
repeated application of f until no residue remains.
Dual to fold/reduce.
f returns either None, or just (value, residue).
For a strict output value, wrap in list().
'''
def go(x):
valueResidue = f(x)
while None is not valueResidue:
yield valueResidue[0]
valueResidue = f(valueResidue[1])
return go
# ---------------------- FORMATTING ----------------------
# chunksOf :: Int -> [a] -> [[a]]
def chunksOf(n):
'''A series of lists of length n, subdividing the
contents of xs. Where the length of xs is not evenly
divisible, the final list will be shorter than n.
'''
def go(xs):
return (
xs[i:n + i] for i in range(0, len(xs), n)
) if 0 < n else None
return go
# spacedTable :: [[String]] -> String
def spacedTable(rows):
'''Tabulated stringification of rows'''
columnWidths = [
max([len(x) for x in col])
for col in zip(*rows)
]
return '\n'.join([
' '.join(
map(
lambda x, w: x.rjust(w, ' '),
row, columnWidths
)
)
for row in rows
])
# MAIN ---
if __name__ == '__main__':
main()</lang>
{{Out}}
<pre>30 terms of the Jacobsthal sequence:
0 1 1 3 5
11 21 43 85 171
341 683 1365 2731 5461
10923 21845 43691 87381 174763
349525 699051 1398101 2796203 5592405
11184811 22369621 44739243 89478485 178956971
30 Jacobsthal-Lucas numbers:
2 1 5 7 17
31 65 127 257 511
1025 2047 4097 8191 16385
32767 65537 131071 262145 524287
1048577 2097151 4194305 8388607 16777217
33554431 67108865 134217727 268435457 536870911
20 Jacobsthal oblong numbers:
0 1 3 15 55
231 903 3655 14535 58311
232903 932295 3727815 14913991 59650503
238612935 954429895 3817763271 15270965703 61084037575
10 primes in the Jacobsthal sequence:
3 5 11 43 683
2731 43691 174763 2796203 715827883</pre>
=={{header|Raku}}==
| |||