Jacobsthal numbers: Difference between revisions
Thundergnat (talk | contribs) (→{{header|Julia}}: mark incorrect for the third time for the same problem) |
(→{{header|Julia}}: Fixed the remaining problem.) |
||
Line 233: | Line 233: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{incorrect|Julia|For the third time... Jacobsthal-Lucas is ''not'' just Jacobsthal shifted left, it is a '''different''' sequence. Deleting the error message does not fix the problem.}} |
|||
<lang julia>using Lazy |
<lang julia>using Lazy |
||
using Primes |
using Primes |
||
J(n) = (2^n - (-1)^n) ÷ 3 |
J(n) = (2^n - (-1)^n) ÷ 3 |
||
L(n) = 2^n + (-1)^n |
|||
Jacobsthal = @>> Lazy.range(0) map(J) |
Jacobsthal = @>> Lazy.range(0) map(J) |
||
JLucas = @>> Lazy.range( |
JLucas = @>> Lazy.range(0) map(L) |
||
Joblong = @>> Lazy.range(big"0") map(n -> J(n) * J(n + 1)) |
Joblong = @>> Lazy.range(big"0") map(n -> J(n) * J(n + 1)) |
||
Jprimes = @>> Lazy.range(big"0") map(J) filter(isprime) |
Jprimes = @>> Lazy.range(big"0") map(J) filter(isprime) |
||
lazyprintnum(s) = println(replace("$s", r"[^\d\,\s]" => "")) |
lazyprintnum(s) = println(replace("$s", r"[^\d\,\s]" => "")) |
||
lazyprintnum(collect(take(30, Jacobsthal))) |
lazyprintnum(collect(take(30, Jacobsthal))) |
||
lazyprintnum(collect(take(30, JLucas))) |
lazyprintnum(collect(take(30, JLucas))) |
||
Line 253: | Line 253: | ||
<pre> |
<pre> |
||
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 |
||
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 |
|||
0, 1, 3, 15, 55, 231, 903, 3655, 14535, 58311, 232903, 932295, 3727815, 14913991, 59650503, 238612935, 954429895, 3817763271, 15270965703, 61084037575 |
0, 1, 3, 15, 55, 231, 903, 3655, 14535, 58311, 232903, 932295, 3727815, 14913991, 59650503, 238612935, 954429895, 3817763271, 15270965703, 61084037575 |
||
3, 5, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243 |
3, 5, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243 |
Revision as of 13:31, 27 February 2022
Jacobsthal numbers are an integer sequence related to Fibonacci numbers. Similar to Fibonacci, where each term is the sum of the previous two terms, each term is the sum of the previous, plus twice the one before that. Traditionally the sequence starts with the given terms 0, 1.
J0 = 0
J1 = 1
Jn = Jn-1 + 2 × Jn-2
Terms may be directly calculated using the formula:
J(n) = ( 2n - (-1)n ) / 3
Jacobsthal-Lucas numbers are very similar. The only difference is an initial starting value J0 = 2 rather than J0 = 0.
Jacobsthal oblong numbers is the sequence obtained from multiplying each two consecutive Jacobsthal numbers together.
Jacobsthal primes are Jacobsthal numbers that are prime.
- Task
- Find and display the first 30 Jacobsthal numbers
- Find and display the first 30 Jacobsthal-Lucas numbers
- Find and display the first 20 Jacobsthal oblong numbers
- Find and display at least the first 10 Jacobsthal primes
- See also
- Wikipedia: Jacobsthal number
- Numbers Aplenty - Jacobsthal number
- OEIS:A001045 - Jacobsthal sequence (or Jacobsthal numbers)
- OEIS:A014551 - Jacobsthal-Lucas numbers.
- OEIS:A084175 - Jacobsthal oblong numbers
- OEIS:A049883 - Primes in the Jacobsthal sequence
- Related task: Fibonacci sequence
- Related task: Leonardo numbers
Factor
<lang factor>USING: grouping io kernel lists lists.lazy math math.functions math.primes prettyprint sequences ;
- 2^-1^ ( n -- 2^n -1^n ) dup 2^ -1 rot ^ ;
- jacobsthal ( m -- n ) 2^-1^ - 3 / ;
- jacobsthal-lucas ( m -- n ) 2^-1^ + ;
- as-list ( quot -- list ) 0 lfrom swap lmap-lazy ; inline
- jacobsthals ( -- list ) [ jacobsthal ] as-list ;
- lucas-jacobthals ( -- list ) [ jacobsthal-lucas ] as-list ;
- prime-jacobsthals ( -- list ) jacobsthals [ prime? ] lfilter ;
- show ( n list -- ) ltake list>array 5 group simple-table. nl ;
- oblong ( -- list )
jacobsthals dup cdr lzip [ product ] lmap-lazy ;
"First 30 Jacobsthal numbers:" print 30 jacobsthals show
"First 30 Jacobsthal-Lucas numbers:" print 30 lucas-jacobthals show
"First 20 Jacobsthal oblong numbers:" print 20 oblong show
"First 20 Jacobsthal primes:" print 20 prime-jacobsthals ltake [ . ] leach</lang>
- Output:
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 First 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 First 20 Jacobsthal oblong numbers: 0 1 3 15 55 231 903 3655 14535 58311 232903 932295 3727815 14913991 59650503 238612935 954429895 3817763271 15270965703 61084037575 First 20 Jacobsthal primes: 3 5 11 43 683 2731 43691 174763 2796203 715827883 2932031007403 768614336404564651 201487636602438195784363 845100400152152934331135470251 56713727820156410577229101238628035243 62357403192785191176690552862561408838653121833643 1046183622564446793972631570534611069350392574077339085483 267823007376498379256993682056860433753700498963798805883563 5562466239377370006237035693149875298444543026970449921737087520370363869220418099018130434731 95562442332919646317117537304253622533190207882011713489066201641121786503686867002917439712921903606443
FreeBASIC
<lang freebasic>Function isPrime(n As Ulongint) As Boolean
If n < 2 Then Return False If n Mod 2 = 0 Then Return false For i As Uinteger = 3 To Int(Sqr(n))+1 Step 2 If n Mod i = 0 Then Return false Next i Return true
End Function
Dim Shared As Uinteger n(1) Dim Shared As Uinteger i0 = 0, i1 = 1 Dim Shared As Integer j, c, P = 1, Q = -2
Print "First 30 Jacobsthal numbers:" c = 0 : n(i0) = 0: n(i1) = 1 For j = 0 To 29
c += 1 Print Using " #########"; n(i0); Print Iif (c Mod 5, "", !"\n"); n(i0) = P * n(i1) - Q * n(i0) Swap i0, i1
Next j
Print !"\n\nFirst 30 Jacobsthal-Lucas numbers: " c = 0 : n(i0) = 2: n(i1) = 1 For j = 0 To 29
c += 1 Print Using " #########"; n(i0); Print Iif (c Mod 5, "", !"\n"); n(i0) = P * n(i1) - Q * n(i0) Swap i0, i1
Next j
Print !"\n\nFirst 20 Jacobsthal oblong numbers: " c = 0 : n(i0) = 0: n(i1) = 1 For j = 0 To 19
c += 1 Print Using " ###########"; n(i0)*n(i1); Print Iif (c Mod 5, "", !"\n"); n(i0) = P * n(i1) - Q * n(i0) Swap i0, i1
Next j
Print !"\n\nFirst 10 Jacobsthal primes: " c = 0 : n(i0) = 0: n(i1) = 1 Do
If isPrime(n(i0)) Then c += 1 : Print n(i0) n(i0) = P * n(i1) - Q * n(i0) Swap i0, i1
Loop Until c = 10 Sleep</lang>
- Output:
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 First 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 First 20 Jacobsthal oblong numbers: 0 1 3 15 55 231 903 3655 14535 58311 232903 932295 3727815 14913991 59650503 238612935 954429895 3817763271 15270965703 61084037575 First 10 Jacobsthal primes: 3 5 11 43 683 2731 43691 174763 2796203 715827883
J
Implementation:
<lang J>ja=: 3 %~ 2x&^ - _1x&^ NB. Jacobsthal jl=: 2x&^ + _1x&^ NB.Jacobsthal-Lucas</lang>
Task examples:
<lang J> ja i.3 10
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
jl i.3 10 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
2 10$2 */\ ja i.21 NB. Jacobsthal oblong 0 1 3 15 55 231 903 3655 14535 58311
232903 932295 3727815 14913991 59650503 238612935 954429895 3817763271 15270965703 61084037575
ja I.1 p:ja i.32 NB. first ten Jacobsthal primes
3 5 11 43 683 2731 43691 174763 2796203 715827883</lang>
Julia
<lang julia>using Lazy using Primes
J(n) = (2^n - (-1)^n) ÷ 3 L(n) = 2^n + (-1)^n
Jacobsthal = @>> Lazy.range(0) map(J) JLucas = @>> Lazy.range(0) map(L) Joblong = @>> Lazy.range(big"0") map(n -> J(n) * J(n + 1)) Jprimes = @>> Lazy.range(big"0") map(J) filter(isprime)
lazyprintnum(s) = println(replace("$s", r"[^\d\,\s]" => ""))
lazyprintnum(collect(take(30, Jacobsthal))) lazyprintnum(collect(take(30, JLucas))) lazyprintnum(collect(take(20, Joblong))) lazyprintnum(collect(take(15, Jprimes)))
</lang>
- Output:
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 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 0, 1, 3, 15, 55, 231, 903, 3655, 14535, 58311, 232903, 932295, 3727815, 14913991, 59650503, 238612935, 954429895, 3817763271, 15270965703, 61084037575 3, 5, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, 201487636602438195784363, 845100400152152934331135470251, 56713727820156410577229101238628035243
Perl
<lang perl>use strict; use warnings; use feature <say state>; use bigint; use List::Util 'max'; use ntheory 'is_prime';
sub table { my $t = 5 * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr }
sub jacobsthal {
my($n) = @_; state @J = (0, 1); do { push @J, $J[-1] + 2 * $J[-2]} until @J > $n; $J[$n];
}
sub jacobsthal_lucas {
my($n) = @_; state @JL = (2, 1); do { push @JL, $JL[-1] + 2 * $JL[-2]} until @JL > $n; $JL[$n];
}
my(@j,@jl,@jo,@jp,$c,$n);
push @j, jacobsthal($_) for 0..29; say "First 30 Jacobsthal numbers:\n", table @j;
push @jl, jacobsthal_lucas($_) for 0..29; say "First 30 Jacobsthal-Lucas numbers:\n", table @jl;
push @jo, $j[$_] * $j[$_+1] for 0..19; say "First 20 Jacobsthal oblong numbers:\n", table @jo;
do { is_prime($n = ( 2**++$c - -1**$c ) / 3) and push @jp, $n } until @jp == 20; say "First 20 Jacobsthal primes:\n", join "\n", @jp;</lang>
- Output:
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 First 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 First 20 Jacobsthal oblong numbers: 0 1 3 15 55 231 903 3655 14535 58311 232903 932295 3727815 14913991 59650503 238612935 954429895 3817763271 15270965703 61084037575 First 20 Jacobsthal primes: 3 5 11 43 683 2731 43691 174763 2796203 715827883 2932031007403 768614336404564651 201487636602438195784363 845100400152152934331135470251 56713727820156410577229101238628035243 62357403192785191176690552862561408838653121833643 1046183622564446793972631570534611069350392574077339085483 267823007376498379256993682056860433753700498963798805883563 5562466239377370006237035693149875298444543026970449921737087520370363869220418099018130434731 95562442332919646317117537304253622533190207882011713489066201641121786503686867002917439712921903606443
Phix
You can run this online here.
with javascript_semantics function jacobsthal(integer n) return floor((power(2,n)+odd(n))/3) end function function jacobsthal_lucas(integer n) return power(2,n)+power(-1,n) end function function jacobsthal_oblong(integer n) return jacobsthal(n)*jacobsthal(n+1) end function printf(1,"First 30 Jacobsthal numbers:\n%s\n", {join_by(apply(true,sprintf,{{"%9d" },apply(tagset(29,0),jacobsthal)}),1,5," ")}) printf(1,"First 30 Jacobsthal-Lucas numbers:\n%s\n", {join_by(apply(true,sprintf,{{"%9d" },apply(tagset(29,0),jacobsthal_lucas)}),1,5," ")}) printf(1,"First 20 Jacobsthal oblong numbers:\n%s\n",{join_by(apply(true,sprintf,{{"%11d"},apply(tagset(19,0),jacobsthal_oblong)}),1,5," ")}) printf(1,"First 10 Jacobsthal primes:\n%s\n", {join(apply(true,sprintf,{{"%d"},filter(apply(tagset(31,0),jacobsthal),is_prime)}),"\n")})
- Output:
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 First 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 First 20 Jacobsthal oblong numbers: 0 1 3 15 55 231 903 3655 14535 58311 232903 932295 3727815 14913991 59650503 238612935 954429895 3817763271 15270965703 61084037575 First 10 Jacobsthal primes: 3 5 11 43 683 2731 43691 174763 2796203 715827883
Python
<lang python>#!/usr/bin/python from math import floor, pow
def isPrime(n):
for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True
def odd(n):
return n and 1 != 0
def jacobsthal(n):
return floor((pow(2,n)+odd(n))/3)
def jacobsthal_lucas(n):
return int(pow(2,n)+pow(-1,n))
def jacobsthal_oblong(n):
return jacobsthal(n)*jacobsthal(n+1)
if __name__ == '__main__':
print("First 30 Jacobsthal numbers:") for j in range(0, 30): print(jacobsthal(j), end=" ")
print("\n\nFirst 30 Jacobsthal-Lucas numbers: ") for j in range(0, 30): print(jacobsthal_lucas(j), end = '\t')
print("\n\nFirst 20 Jacobsthal oblong numbers: ") for j in range(0, 20): print(jacobsthal_oblong(j), end=" ")
print("\n\nFirst 10 Jacobsthal primes: ") for j in range(3, 33): if isPrime(jacobsthal(j)): print(jacobsthal(j))</lang>
Raku
<lang perl6>my $jacobsthal = cache lazy 0, 1, * × 2 + * … *; my $jacobsthal-lucas = lazy 2, 1, * × 2 + * … *;
say "First 30 Jacobsthal numbers:"; say $jacobsthal[^30].batch(5)».fmt("%9d").join: "\n";
say "\nFirst 30 Jacobsthal-Lucas numbers:"; say $jacobsthal-lucas[^30].batch(5)».fmt("%9d").join: "\n";
say "\nFirst 20 Jacobsthal oblong numbers:"; say (^∞).map( { $jacobsthal[$_] × $jacobsthal[$_+1] } )[^20].batch(5)».fmt("%11d").join: "\n";
say "\nFirst 20 Jacobsthal primes:"; say $jacobsthal.grep( &is-prime )[^20].join: "\n";</lang>
- Output:
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 First 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 First 20 Jacobsthal oblong numbers: 0 1 3 15 55 231 903 3655 14535 58311 232903 932295 3727815 14913991 59650503 238612935 954429895 3817763271 15270965703 61084037575 First 20 Jacobsthal primes: 3 5 11 43 683 2731 43691 174763 2796203 715827883 2932031007403 768614336404564651 201487636602438195784363 845100400152152934331135470251 56713727820156410577229101238628035243 62357403192785191176690552862561408838653121833643 1046183622564446793972631570534611069350392574077339085483 267823007376498379256993682056860433753700498963798805883563 5562466239377370006237035693149875298444543026970449921737087520370363869220418099018130434731 95562442332919646317117537304253622533190207882011713489066201641121786503686867002917439712921903606443
Wren
<lang ecmascript>import "./big" for BigInt import "./seq" for Lst import "./fmt" for Fmt
var jacobsthal = Fn.new { |n| ((BigInt.one << n) - ((n%2 == 0) ? 1 : -1)) / 3 }
var jacobsthalLucas = Fn.new { |n| (BigInt.one << n) + ((n%2 == 0) ? 1 : -1) }
System.print("First 30 Jacobsthal numbers:") var js = (0..29).map { |i| jacobsthal.call(i) }.toList for (chunk in Lst.chunks(js, 5)) Fmt.print("$,12i", chunk)
System.print("\nFirst 30 Jacobsthal-Lucas numbers:") var jsl = (0..29).map { |i| jacobsthalLucas.call(i) }.toList for (chunk in Lst.chunks(jsl, 5)) Fmt.print("$,12i", chunk)
System.print("\nFirst 20 Jacobsthal oblong numbers:") var oblongs = (0..19).map { |i| js[i] * js[i+1] }.toList for (chunk in Lst.chunks(oblongs, 5)) Fmt.print("$,14i", chunk)
var primes = js.where { |j| j.isProbablePrime(10) }.toList var count = primes.count var i = 31 while (count < 20) {
var j = jacobsthal.call(i) if (j.isProbablePrime(10)) { primes.add(j) count = count + 1 } i = i + 1
} System.print("\nFirst 20 Jacobsthal primes:") for (i in 0..19) Fmt.print("$i", primes[i])</lang>
- Output:
First 30 Jacobsthal numbers: 0 1 1 3 5 11 21 43 85 171 341 683 1,365 2,731 5,461 10,923 21,845 43,691 87,381 174,763 349,525 699,051 1,398,101 2,796,203 5,592,405 11,184,811 22,369,621 44,739,243 89,478,485 178,956,971 First 30 Jacobsthal-Lucas numbers: 2 1 5 7 17 31 65 127 257 511 1,025 2,047 4,097 8,191 16,385 32,767 65,537 131,071 262,145 524,287 1,048,577 2,097,151 4,194,305 8,388,607 16,777,217 33,554,431 67,108,865 134,217,727 268,435,457 536,870,911 First 20 Jacobsthal oblong numbers: 0 1 3 15 55 231 903 3,655 14,535 58,311 232,903 932,295 3,727,815 14,913,991 59,650,503 238,612,935 954,429,895 3,817,763,271 15,270,965,703 61,084,037,575 First 20 Jacobsthal primes: 3 5 11 43 683 2731 43691 174763 2796203 715827883 2932031007403 768614336404564651 201487636602438195784363 845100400152152934331135470251 56713727820156410577229101238628035243 62357403192785191176690552862561408838653121833643 1046183622564446793972631570534611069350392574077339085483 267823007376498379256993682056860433753700498963798805883563 5562466239377370006237035693149875298444543026970449921737087520370363869220418099018130434731 95562442332919646317117537304253622533190207882011713489066201641121786503686867002917439712921903606443