Fermat numbers: Difference between revisions

=={{header|jq}}==

'''Works with gojq, the Go implementation of jq'''

'''Preliminaries'''

<lang jq># To take advantage of gojq's arbitrary-precision integer arithmetic:

def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);

def gcd(a; b):

# subfunction expects [a,b] as input

# i.e. a ~ .[0] and b ~ .[1]

def rgcd: if .[1] == 0 then .[0]

else [.[1], .[0] % .[1]] | rgcd

end;

[a,b] | rgcd;

# This is fast because the state of `until` is just a number

def is_prime:

. as $n

| if ($n < 2) then false

elif ($n % 2 == 0) then $n == 2

elif ($n % 3 == 0) then $n == 3

elif ($n % 5 == 0) then $n == 5

elif ($n % 7 == 0) then $n == 7

elif ($n % 11 == 0) then $n == 11

elif ($n % 13 == 0) then $n == 13

elif ($n % 17 == 0) then $n == 17

elif ($n % 19 == 0) then $n == 19

elif ($n % 23 == 0) then $n == 23

elif ($n % 29 == 0) then $n == 29

elif ($n % 31 == 0) then $n == 31

elif ($n % 37 == 0) then $n == 37

elif ($n % 41 == 0) then $n == 41

else 43

| until( (. * .) > $n or ($n % . == 0); . + 2)

| . * . > $n

end;</lang>

'''Fermat Numbers'''

<lang jq>def fermat:

. as $n

| (2 | power( 2 | power($n))) + 1;

# https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

def pollardRho($x):

. as $n

| def g: (.*. + 1) % $n ;

{x:$x, y:$x, d:1}

| until(.d != 1;

.x |= g

| .y |= (g|g)

| .d = gcd((.x - .y)|length; $n) )

| if .d == $n then 0

else .d

end ;

def rhoPrimeFactors:

. as $n

| pollardRho(2)

| if . == 0

then [$n, 1]

else [., ($n / .)]

end ;

"The first 10 Fermat numbers are:",

[ range(0;10) | fermat ] as $fns

| (range(0;10) | "F\(.) is \($fns[.])"),

("\nFactors of the first 7 Fermat numbers:",

range(0;7) as $i

| $fns[$i]

| rhoPrimeFactors as $factors

| if $factors[1] == 1

then "F\($i) : rho-prime", " ... => \(if is_prime then "prime" else "not" end)"

else "F\($i) => \($factors)"

end )</lang>

{{out}}

<pre>

The first 10 Fermat numbers are:

F0 is 3

F1 is 5

F2 is 17

F3 is 257

F4 is 65537

F5 is 4294967297

F6 is 18446744073709551617

F7 is 340282366920938463463374607431768211457

F8 is 115792089237316195423570985008687907853269984665640564039457584007913129639937

F9 is 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097

Factors of the first 7 Fermat numbers:

F0 : rho-prime

... => prime

F1 : rho-prime

... => prime

F2 : rho-prime

... => prime

F3 : rho-prime

... => prime

F4 : rho-prime

... => prime

F5 => [641,6700417]

F6 => [274177,67280421310721]

</pre>