Jacobsthal numbers: Difference between revisions
Content added Content deleted
(→{{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: | Line 1,285: | ||
{{out}} |
{{out}} |
||
<pre>First 30 Jacobsthal numbers: |
|||
<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 |
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: | Line 1,304: | ||
174763 |
174763 |
||
2796203 |
2796203 |
||
715827883 |
715827883</pre> |
||
</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}}== |
=={{header|Raku}}== |