Penta-power prime seeds: Difference between revisions

=={{header|jq}}==

The specified tasks are beyond the capabilties of the current

implementations of jq:

* The C implementation (jq) does not support unbounded-precision integer arithmetic, and so is in effect only capable of generating the first few penta-power prime (ppp) seeds.

* The Go implementation (gojq) does support unbounded-precision integer arithmetic and the following program has been used to generate the first 13 ppp seeds, but gojq takes a long while to do so; other variants of the program have been considered but they run into gojq's memory-management limitations.

The program given below may nevertheless be of some interest as it

illustrates how a JSON dictionary can be used to cache the primes up

to a certain limit, and how this can be done using a sieve

economically:

<syntaxhighlight lang=jq>

# Create a dictionary for the primes up to .

def primeDictionary:

# The array we use for the sieve only stores information for the odd integers greater than 1:

# index integer

# 0 3

# k 2*k + 3

# So if we wish to mark m = 2*k + 3, the relevant index is: m - 3 / 2

def ix:

if . % 2 == 0 then null

else ((. - 3) / 2)

end;

# erase(i) sets .[i*j] to false for odd integral j > i, and assumes i is odd

def erase(i):

((i - 3) / 2) as $k

# Consider relevant multiples:

| (((length * 2 + 3) / i)) as $upper

# ... only consider odd multiples from i onwards

| reduce range(i; $upper; 2) as $j (.;

(((i * $j) - 3) / 2) as $m

| if .[$m] then .[$m] = false else . end);

if . < 2 then {}

else (. + 1) as $n

| (($n|sqrt) / 2) as $s

| [range(3; $n; 2)|true]

| reduce (1 + (2 * range(1; $s)) ) as $i (.; erase($i))

| . as $sieve

| reduce (2, (range(3; $n; 2) | select($sieve[ix]))) as $i ({}; .[$i|tostring]=$i)

end ;

</syntaxhighlight>

<syntaxhighlight lang=jq>

# Input should be an integer

def isPrime:

. as $n

| if ($n < 2) then false

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

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

else 5

| until( . <= 0;

if .*. > $n then -1

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

else . + 2

| if ($n % . == 0) then 0

else . + 4

end

end)

| . == -1

end;

# $primedictionary should be a dictionary of primes up to $small

def ispentapowerprime($primedictionary; $small):

def isp: if . <= $small then $primedictionary[tostring] else isPrime end;

. as $n

| (. * .) as $n2

| (. * $n2) as $n3

| all($n + 2, $n + $n + 1, $n2 + $n + 1, $n3 + $n + 1, $n3 * $n + $n + 1; isp);

# Output: a stream of the first $count penta-power prime-seeds

# The size of the dictionary has been chosen with gojq in mind.

def ppprimes($count):

# The size of primeDictionary has been chosen with gojq's limitations in mind

($count | .*.*. | primeDictionary) as $pd

| limit($count; 1, 2, range(3; infinite; 2) | select(ispentapowerprime($pd; $small)) );

ppprimes(30)

</syntaxhighlight>

{{output}}

Using gojq, progress effectively grinds to a halt after 207285.

<pre>

1

5

69

1665

2129

25739

29631

62321

77685

80535

82655

126489

207285

<terminated>

</pre>