Partition an integer x into n primes: Difference between revisions

=={{header|jq}}==

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

'''Prime-number functions'''

<lang jq>

# Is the input integer a prime?

def is_prime:

if . == 2 then true

else 2 < . and . % 2 == 1 and

. as $in

| (($in + 1) | sqrt) as $m

| (((($m - 1) / 2) | floor) + 1) as $max

| all( range(1; $max) ; $in % ((2 * .) + 1) > 0 )

end;

# Is the input integer a prime?

# `previous` should be a sorted array of consecutive primes

# greater than 1 and at least including the greatest prime less than (.|sqrt)

def is_prime(previous):

. as $in

| (($in + 1) | sqrt) as $sqrt

| first(previous[]

| if . > $sqrt then 1

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

else empty

end) // 1

| . == 1;

# This assumes . is an array of consecutive primes beginning with [2,3]

def next_prime:

. as $previous

| (2 + .[-1] )

| until(is_prime($previous); . + 2) ;

# Emit primes from 2 up

def primes:

# The helper function has arity 0 for TCO

# It expects its input to be an array of previously found primes, in order:

def next:

. as $previous

| ($previous|next_prime) as $next

| $next, (($previous + [$next]) | next) ;

2, 3, ([2,3] | next);

# The primes less than or equal to $x

def primes($x):

label $out

| primes | if . > $x then break $out else . end;

</lang>

'''Helper function'''

<lang jq># Emit a stream consisting of arrays, a, of $n items from the input array,

# preserving order, subject to (a|add) == $sum

def take($n; $sum):

def take:

. as [$m, $in, $s]

| if $m==0 and $s == 0 then []

elif $m==0 or $s <= 0 then empty

else range(0;$in|length) as $i

| $in[$i] as $x

| if $x > $s then empty

else [$x] + ([$m-1, $in[$i+1:], $s - $x] | take)

end

end;

[$n, ., $sum] | take;</lang>

'''Partitioning an integer into $n primes'''

<lang jq># This function emits a possibly empty stream of arrays.

# Assuming $primes is primes(.), each array corresponds to a

# partition of the input into $n distinct primes.

# The algorithm is unoptimized.

# The output is a stream of arrays, which would be empty

def primepartition($n; $primes):

. as $x

| if $n == 1

then if $primes[-1] == $x then [$x] else null end

else (if $primes[-1] == $x then $primes[:-1] else $primes end) as $primes

| ($primes | take($n; $x))

end ;

# See primepartition/2

def primepartition($n):

. as $x

| if $n == 1

then if is_prime then [.] else null end

else primepartition($n; [primes($x)])

end;

# Compute first(primepartition($n)) for each $n in the array $ary

def primepartitions($ary):

. as $x

| [primes($x)] as $px

| $ary[] as $n

| $x

| first(primepartition($n; $px));

def task($x; $n):

def pp:

if . then join("+") else "(not possible)" end;

if $n|type == "array" then task($x; $n[])

else "A partition of \($x) into \($n) parts: \(first($x | primepartition($n)) | pp )"

end;

</lang>

'''The tasks'''

<lang jq>task(18; 2),

task(19; 3),

task(20; 4),

task(2017; 24),

task(22699; [1,2,3,4]),

task(40355; 3)</lang>

{{out}}

<pre>

A partition of 18 into 2 parts: 5+13

A partition of 19 into 3 parts: 3+5+11

A partition of 2017 into 24 parts: 2+3+5+7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+97+1129

A partition of 22699 into 1 parts: 22699

A partition of 22699 into 2 parts: 2+22697

A partition of 22699 into 3 parts: 3+5+22691

A partition of 22699 into 4 parts: 2+3+43+22651

A partition of 40355 into 3 parts: 3+139+40213

</pre>