# Prime a*b+c of N

Given an integer $$\N\$$, print or return integers $$\a\$$, $$\b\$$, and $$\c\$$ that satisfy all of the following conditions, if such integers exist:

• $$\a \times b + c = N\$$
• $$\a\$$, $$\b\$$, and $$\c\$$ are all prime
• $$\a > b > c\$$

If no valid combination of integers exist, you should return nothing, 0, None, an empty list, or raise an error.

If multiple valid combinations of integers exists, you can print or return any of them or all of them in a data type of your choosing.

A list of multiple solutions does not need to be sorted, and since we know that $$\a > b > c\$$, you can return them in any order.

Examples:

Input: 17
Output: 5 3 2

Input: 20
Output: None

Input: 37
Output: 7 5 2

Input: 48
Output: None

Input: 208
Output: [(41, 5, 3), (29, 7, 5)]


This is code golf, so the code with the lowest byte count wins.

Inspired by this Redditor's neat dream.

# Wolfram Mathematica, 29 bytes

 Solve[a*b+c==#>a>b>c,Primes]&


Test cases:

Solve[a*b+c==#>a>b>c,Primes]&@17
Solve[a*b+c==#>a>b>c,Primes]&@20
Solve[a*b+c==#>a>b>c,Primes]&@37
Solve[a*b+c==#>a>b>c,Primes]&@48
Solve[a*b+c==#>a>b>c,Primes]&@208


{{a -> 5, b -> 3, c -> 2}}

{}

{{a -> 7, b -> 5, c -> 2}}

{}

{{a -> 29, b -> 7, c -> 5}, {a -> 41, b -> 5, c -> 3}}

# tinylisp, 210 bytes

(load library
(d p prime?
(d f(q((n k)(i(e n k)0(i(g n k 2)(g n k 2)(f n(+ k 1
(d g(q((n k j)(i(l(/ n k)j)0(i(*(l(- n(* k j))j)(l j k)(p(- n(* k j)))(p k)(p j))(list k(- n(* k j))j)(g n k(+ j 1
(d F(q((n)(f n 2


Try it online!

Gotta love golfing in tinylisp...

Thanks to DLosc for saving some bytes... 32 to be exact.

# Factor + math.combinatorics math.primes, 64 bytes

[ dup nprimes swap 3 [ first3 * + = ] with filter-combinations ]


Try it online!

## Explanation

Get all the combinations of three primes that satisfy a * b + c = N. a > b > c is inherent by virtue of the fact we're filtering combinations without repetition.

# Pyth, 37 bytes

FGQIP_GFHGIP_HFNHIP_NIq+*GHNQ
G
H
N.q


hacky, but works

Try it online!

explanation:

                              Q = eval(input())
F                             for
G                            G
Q                           in range(Q):
I                            if
P_                          prime(
G                          G
):
F                          for
H                         H
G                        in range(G):
I                         if
P_                       prime(
H                       H
):
F                      for
N                     H
H                    in range(H):
I                     if
P_                   prime(
N                   N
):
I                   if
G               G
*                *
H              H
+                 +
N             N
q                  ==
Q            Q:
(newline)     print(
G                                             G
)
(newline)                                  print(
H                                             H
)
(newline)                                  print(
N                                             N
)
.q                                         exit()


# Excel, 164 bytes

=TEXTJOIN(",",,LET(q,SEQUENCE(A4),a,FILTER(q,MMULT((MOD(q,TRANSPOSE(q))=0)*1,q^0)=2),b,TRANSPOSE(a),c,(a>b)*(A4-a*b),IF(XLOOKUP(c,a,a^0,0)*(b>c),a&" "&b&" "&c,"")))


## Explantion

=TEXTJOIN(",",, ~ )                 # Separates multiple answers with a comma
LET(q,SEQUENCE(A4),               # q = (1..A4) listed vertically
a,FILTER(q, ~ ),                  # a = primes in q
MMULT( ~,q^0)=2                 # a number is prime if the sum of the row is 2
MOD(q,TRANSPOSE(q))=0)*1      # creates a qxq array where if row# mod column = 0 then 1 else 0
b,TRANSPOSE(a),                   # b primes listed horizontally
c,(a>b)*(A4-a*b),                 # 2-dim array where if a>b then c = A4 - a*b
IF(XLOOKUP(c,a,a^0,0)*(b>c),~,"") # if c is prime and b>c then return value else ""
a&" "&b&" "&c                   # a b c


## Insider Beta Version using LAMBDA, 157 bytes

=TEXTJOIN(",",,MAKEARRAY(A1,A1,LAMBDA(a,b,LET(c,MAX(A1-a*b,1),p,LAMBDA(x,SUM((MOD(x,SEQUENCE(x))=0)*1)=2),IF((a>b)*(b>c)*p(a)*p(b)*p(c),a&" "&b&" "&c,"")))))


# APL(Dyalog Unicode) + dfns, 6343 bytes SBCS

{⍵⌿⍨(∧/1pco¨⍵)∧⍺=(0∘⌷+1∘⌷×2∘⌷)⍉⍵}∘(3cmat⊢)⍨


Hats off to @ovs for a 2+18 bytes shave!

Tacit function with an anonymous function baked in. Returns a 3-col matrix, with as many rows as possible results.

dfns is like a library of useful functions:

• the pco function I'm using, which checks for primality, can be found there; and
• the cmat function generates the combinations of possible a, b, and c values.

Try it on online! The TIO link has 2 more bytes because of f←, which I'm using to make it easier to test the function. It also takes a long time because I'm being wasteful with my primality checks; here is the output on my machine:

      f¨ 17 20 37 48 208
┌─────┬┬─────┬┬──────┐
│5 3 2││7 5 2││29 7 5│
│     ││     ││41 5 3│
└─────┴┴─────┴┴──────┘


Explanation:

(3cmat⊢) builds a 3-column matrix with all possible values of a, b, and c, already satisfying the restriction that a > b > c:

      (3cmat⊢) 4
0 1 2
0 1 3
0 2 3
1 2 3


Then, {⍵⌿⍨(∧/1pco¨⍵)∧⍺=(0∘⌷+1∘⌷×2∘⌷)⍉⍵} takes the original number on the left and that 3-col matrix on the right, and takes all rows that satisfy two criteria simultaneously:

• the rows only have prime numbers (checked with (∧/1pco¨⍵)); and
• a×b+c equals the original input (checked with ⍺=(0∘⌷+1∘⌷×2∘⌷)⍉⍵).
• You can save 2 bytes by not assigning b and use ⍵⌿⍨(∧/1pco¨⍵)∧⍺=... instead. And if you want to go full library cmat should be able to replace most of the right part
– ovs
Feb 2 at 15:19
• @ovs Great catch! Using cmat saved a whopping 18 bytes!
– RGS
Feb 2 at 15:39

# MATL, 282524 23 bytes

Zq"@tG-YfhXHd0>AHn3=*?H


Try it online!

Zq"   % for each prime less than (or equal to) the input
@t    % duplicate it on the stack
G-    % subtract it from the input
Yf    % get the prime factors of the result
h     % concatenate that with the current iterating prime
XH    % save that in the H clipboard
d0>A  % check that it's strictly increasing
Hn3=  % and has 3 elements
*?    % if both conditions are true
H     % push that result list back on the stack


Prints all valid results.

# Vyxal, 10 bytes

~æ3ḋ'÷*+?=


Try it Online!

~          # Filter (implicit) range 1...n by...
æ         # Is prime?
3ḋ       # Combinations of length 3
'      # Filtered by...
÷*+   # a*b+c
?= # Equals input?


Outputs a list of all valid lists.

• I don't think this is a valid submission. The algorithm here is a semi-decision algorithm, meaning it goes to an infinite loop when it encounters a number that doesn't have a solution, but OP asked for a deciding algorithm. Usually things like memory exhaustion are ignored in code golf. It's fine to say that the memory exhaustion is part of the algorithm, but now this algorithm can only calculate a finite amount of N:s, since if N is very large, the memory exhaustion will happen, even if N has a solution. Jan 31 at 20:39
• @AnttiP The memory exhaustion will always eventually happen on any machine if impossible. But this can calculate any value on a machine with enough memory to do so. Jan 31 at 20:55
• Hmm, I still disagree, but I think this would better be discussed in meta. Jan 31 at 20:59
• @AnttiP Agreed. Also see l4m2's second solution. Jan 31 at 21:00
• It seems that concensus has gone in favor of this being invalid (codegolf.meta.stackexchange.com/questions/24411/…). Feb 5 at 5:51

# JavaScript (Node.js), 89 bytes

f=(n,b)=>p(b)&p(a=n/b|0)&p(c=n%b)&a>b?[a,b,c]:b!=n&&f(n,-~b);p=(n,i=n)=>n%--i?p(n,i):i==1


Try it online!

If stackoverflow allowed as an error, then

# JavaScript (Node.js), 83 bytes

f=(n,b)=>p(b)&p(a=n/b|0)&p(c=n%b)&a>b?[a,b,c]:f(n,-~b);p=(n,i=n)=>n%--i?p(n,i):i==1


Try it online!

# Python 3, 137 bytes

lambda n:[(a,b,c)for a in R(n)for b in R(n)for c in R(n)if all([a>b>c,a*b+c==n,all(all(n%m for m in R(2,n))for n in (a,b,c)),c])]
R=range


Try it online!

Thanks to @attiP for R=range -8 bytes

# Python 3, 139 bytes

eval("lambda n:[(a,b,c)for aRfor bRfor cRif all([a>b>c,a*b+c==n,all(all(n%m for mR[2:])for n in (a,b,c)),c])]".replace("R"," in range(n)"))


Try it online!

• You can do just R=range for 137 bytes: Try it online! Feb 13 at 15:59

# Python 2, 112 bytes

P=k=1
p=r=[]
n=input()
while k<n:
if P%k:r=r+[(k,b,n-k*b)for b in p if b>n-k*b in p];p+=k,
P*=k*k;k+=1
print r


Try it online!

A port of l4m2's Javascript answer with a bit of their help comes in at 101 99 bytes:

f=lambda n,b=1:all(p%k for p in(n/b,b,n%b)for k in range((n%b>1)+(n/b>b),p))*(n/b,b,n%b)or f(n,b+1)


Try it online!

• Do this work?
– l4m2
Jan 31 at 10:49
• That's a great python 2 answer. Jan 31 at 18:06

# Jelly (fork), 10 bytes

ÆRUŒƈ×+ƭ/Ƙ


Try it online! (the Jelly equivalent)

Outputs all possible solutions, or [] if there are none. And, the equivalent vanilla Jelly answer:

# Jelly, 13 bytes

ÆRUœc3×+ƭ/=¥Ƈ


Try it online!

## How they work

ÆRUŒƈ×+ƭ/Ƙ - Main link. Takes an integer N on the left
ÆR         - Primes from 2 to N
U        - Reverse
Œƈ      - Combinations of 3, no replacement
Ƙ - Keep those that equal N under:
/  -   Reduce [a, b, c] by:
ƭ   -     Tie two dyads f, g:
×     -       Product
This maps [a, b, c] -> [a×b, c] -> a×b+c


The normal Jelly one is identical, except that œc3 is special-cased as Œƈ and =¥Ƈ is equivalent to Ƙ

->n{(2..n).select{|x|/^(!!+)\1+$/!~?!*x}.combination(3).find{|c,b,a|a*b+c==n}}  Try it online! • I gather 1 isn't a prime? You can fix this by using Prime.take(n), and either including require'prime' or -rprime as a flag. Jan 31 at 21:57 # Husk, 14 bytes ḟo=⁰§+←oΠtṖ3İp  Try it online! Outputs c<b<a if a solution exists, otherwise quits after 1 minute with a 'the request exceeded the 60 second time limit and was terminated' warning from the 'try it online' interpreter. Arguably this isn't a real 'error' (and Husk itself would happily run forever looking for a solution among higher and higher entries in the infinite list of primes), so for 1 more byte we can have: ḟo=¹§+←oΠtṖ3fṗḣ (which only searches among primes less than the input). ḟo # return the first... Ṗ3 # ...list of 3 items selected from İp # ...the infinite list of primes # that satisfies: §+ # the sum of... ← # ...the first item oΠ # ...and the product of t # ...the tail (all except first item) =⁰ # is equal to the input  # PowerShell Core, 176 bytes param($n)for($c=1;++$c-lt$n){for($b=$c;++$b-lt$n){for($a=$b;++$a-lt$n){if($a*$b+$c-eq$n-and(&($p={param($t)!($t-2)-!(2..($t-1)|?{!($t%$_)})})$a)*(&$p$b)*(&$p$c)){$a,$b,$c}}}}  Try it online! I tried using ranges, but it gets really slow, probably because it is allocating too many of them, so for for now :) Slow draft with ranges, 175 bytes # C (gcc), 139 130 122 118 115 bytes a,b,c,z,y;p(x){for(y=z=1;++z<x;)y&=x%z>0;y=!y;}f(n){for(a=n;a&&p(c=(c<3?b<3?b=--a-1:--b:c)-1)|p(b)|p(a)|a*b+c-n;);}  Try it online! Slightly golfed less. a,b,c,z,y; p(x){ y=z=1; for(;++z<x;) y&=x%z>0; y=!y; } f(n){ a=n; while(a&&p(c=(c<3?b<3?b=--a-1:--b:c)-1)|p(b)|p(a)|a*b+c-n); }  # 80386 Machine Code, 110107 99 bytes Try it online! When there is no valid answer, the program crashes, and I hope this belongs to "raise an error" category. Thanks for the wonderful tip for skipping instructions. I'm still trying to get rid of the calls which take 5 bytes each, but it's not clear for now. ecx is the input number, and edx is the pointer to the output array 00000000 <f>: 0: 89 cf mov edi,ecx 2: 31 db xor ebx,ebx 4: 89 d8 mov eax,ebx 00000006 <L0>: 6: e3 40 jecxz 48 <err> 8: 83 f8 02 cmp eax,0x2 b: 7f 0b jg 18 <_1> d: 83 fb 02 cmp ebx,0x2 10: 7f 03 jg 15 <_0> 12: 49 dec ecx 13: 89 cb mov ebx,ecx 00000015 <_0>: 15: 4b dec ebx 16: 89 d8 mov eax,ebx 00000018 <_1>: 18: 48 dec eax 19: 89 c5 mov ebp,eax 1b: e8 29 00 00 00 call 49 <p> 20: 73 e4 jae 6 <L0> 22: 89 dd mov ebp,ebx 24: e8 20 00 00 00 call 49 <p> 29: 73 db jae 6 <L0> 2b: 89 cd mov ebp,ecx 2d: e8 17 00 00 00 call 49 <p> 32: 73 d2 jae 6 <L0> 34: 89 ce mov esi,ecx 36: 0f af f3 imul esi,ebx 39: 01 c6 add esi,eax 3b: 39 fe cmp esi,edi 3d: 75 c7 jne 6 <L0> 3f: 89 0a mov DWORD PTR [edx],ecx 41: 89 5a 04 mov DWORD PTR [edx+0x4],ebx 44: 89 42 08 mov DWORD PTR [edx+0x8],eax 47: c3 ret 00000048 <err>: 48: f4 hlt 00000049 <p>: 49: 50 push eax 4a: 51 push ecx 4b: 52 push edx 4c: 89 e9 mov ecx,ebp 0000004e <L1>: 4e: 49 dec ecx 4f: 83 f9 02 cmp ecx,0x2 52: 7c 0a jl 5e <end> 54: 89 e8 mov eax,ebp 56: 99 cdq 57: f7 f1 div ecx 59: 85 d2 test edx,edx 5b: 75 f1 jne 4e <L1> 5d: a8 .byte 0xa8 0000005e <end>: 5e: f9 stc 5f: 5a pop edx 60: 59 pop ecx 61: 58 pop eax 62: c3 ret  output 5 3 2 7 5 2 41 5 3 47 7 5  the original assembly code • Nice! And yes, a crashed program is a fair result. Mar 2 at 22:30 # Retina 0.8.2, 120 bytes .+$*
^(11(1)+)(?<!^\3+(11+))((?<9-2>\1))+(?!1?$|(11+)\5+$)((?<-4>1)+)$(?<=(?!(11+)\7+$)((?>1(?<-9>1)+)))|.+
$.1$.8 $.6  Try it online! Link includes test cases. Explanation: .+$*


Convert to unary.

^(11(1)+)(?<!^\3+(11+))


Search for a prime number a ($.1 or 2+$#2)...

((?<9-2>\1))+


... that when repeated b (1+$#4 or 1+$#9) times ($#4/$#9 is less than or equal to $#2 so b is less than a)... (?!1?$|(11+)\5+$)((?<-4>1)+)$


... leaves a remainder c ($.6) that is prime ($.6 is less than or equal to $#4 so c is less than b)... (?<=(?!(11+)\7+$)((?>1(?<-9>1)+)))


... and b ($.8) is prime. |.+  But if a match couldn't be found, replace the input anyway. $.1 $.8$.6


Replace the input with the desired values.

# Python 3, 174 bytes

from itertools import*
f=lambda n:[i for i in [(a,b,c)for a,b,c in combinations([*range(n-1,-1,-1)],3)if a*b+c==n]if all(map(lambda n:all(n%i for i in range(2,n))==(n>1),i))]


Try it online!

# Python 3.8 (pre-release), 138 bytes

lambda i,F=lambda n:all(n%a for a in range(2,n)):[[j,k,l]for j in range(3,i)for k in range(3,i//j+1)if F(j)+F(k)+F(l:=i-j*k)>2<=l<k<j][:1]


Try it online!

Semi-brute-force method. Thanks AnttiP for spotting an obvious superfluous 5-byte segment.

• Isn't 2<=l|0==l the same as 2<=l? Jan 31 at 20:44
• @AnttiP of course, that l|0 thing was just something from my previous code. Will fix. Feb 1 at 6:15

# 05AB1E, 10 bytes

ÅP3.Æʒ*+Q


Outputs the triplets in the order $$\[c,b,a]\$$.

Explanation:

ÅP          # Push a list of prime numbers ≤ the (implicit) input-integer
3.Æ       # Get all unique 3-element combinations of this list
ʒ      # Filter these [c,b,a]-triplets by:
#  Pop and push c,b,a separated to the stack
*    #  Multiply the top two: b*a
+   #  Add it to the third: c+b*a
Q  #  Check if it's equal to the (implicit) input-integer
# (after which the filtered list of triplets is output implicitly)


# Charcoal, 39 bytes

ＮθＩΦＥ…²θ⟦ι÷θι﹪θι⟧∧⬤⊞ＯΦιμ¹‹λ§ιμ⬤ι⬤…²λ﹪λν


Try it online! Link is to verbose version of code. Outputs all solutions. Explanation: Test all values a from 2 up to n and checks that the list [a, n/a, n%a, 1] is descending and that the first three elements are prime. Conveniently this optimised version turns out to be golfier than a naïve brute force algorithm.

Ｎθ                                      Input as an integer
…                                  Range from
²                                 Literal integer 2
θ                                To input integer
Ｅ                                   Map over values
ι                              Current value
θ                            Input integer
÷                             Integer divided by
ι                           Current value
θ                         Input integer
﹪                          Modulo
ι                        Current value
⟦       ⟧                       Make into a list
Φ                                    Filtered where
ι                Current list
Φ                 Filtered where
μ               Inner index
⊞Ｏ                  Concatenated with
¹               Literal integer 1
⬤                     All values satisfy
λ             Current value
‹              Is less than
ι           Current list
§            Indexed by
μ          Inner index
∧                      Logical And
ι        Current list
⬤         All elements satisfy
…      Range from
²     Literal integer 2
λ    To current element
⬤       All values satisfy
λ  Current element
﹪   Is not divisible by
ν Innermost value
Ｉ                                         Cast to string
Implicitly print


# BQN, 37 bytesSBCS

Main idea taken from l4m2's answer.

(∨⊸≡∧´(1=·+´0=↕⊸|)¨)¨⊸/⊢(⌊÷∾⊢∾|˜)¨1↓↕


Run online!

# APL (Dyalog Unicode) + dfns, 29 bytes

I spent a bit too much time trying to golf RGS's answer, so I decided to post this on its own now.

{m⌿⍨⍵=2(⌷+0⌷×⌿)⍉m←pco⌽3cmat⍵}


Try it online!

There are two significant differences compared to the original answer:

• When pco is applied to a single argument, it returns the ⍵-th prime number. This can be used to construct triples of primes directly, avoiding a more complicated primality test.
• The implementation for $$\a\times b+c\$$ is a bit shorter using dyadic / to get the product.

# Japt, 16 bytes

... So very out of practice. Returns all possible solutions, each in reverse order.

o ðj à f@¶XÎ+XÅ×


Try it

# Julia 0.4, 62 bytes

N->for a=P=primes(N),b=P,c=P a>b>c&&a*b+c==N&&return a,b,c end


Try it online!

Julia 0.4 for the primes function (later moved in the Primes package). Returns nothing is there is no solution

# Haskell, 91 bytes

f n=[[a,b,c]|a<-q\$n+1,b<-q a,c<-q b,a*b+c==n,and[0<mod y x|y<-[a,b,c],x<-q y]];q z=[2..z-1]


Try it online!