18
\$\begingroup\$

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.

\$\endgroup\$
0

27 Answers 27

11
\$\begingroup\$

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}}

\$\endgroup\$
6
+50
\$\begingroup\$

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.

\$\endgroup\$
0
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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()
\$\endgroup\$
3
\$\begingroup\$

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,"")))

Link to Spreadsheet

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,"")))))
\$\endgroup\$
3
\$\begingroup\$

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∘⌷)⍉⍵).
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – ovs
    Feb 2 at 15:19
  • \$\begingroup\$ @ovs Great catch! Using cmat saved a whopping 18 bytes! \$\endgroup\$
    – RGS
    Feb 2 at 15:39
2
\$\begingroup\$

MATL, 28 25 24 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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – AnttiP
    Jan 31 at 20:39
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – emanresu A
    Jan 31 at 20:55
  • \$\begingroup\$ Hmm, I still disagree, but I think this would better be discussed in meta. \$\endgroup\$
    – AnttiP
    Jan 31 at 20:59
  • \$\begingroup\$ @AnttiP Agreed. Also see l4m2's second solution. \$\endgroup\$
    – emanresu A
    Jan 31 at 21:00
  • \$\begingroup\$ It seems that concensus has gone in favor of this being invalid (codegolf.meta.stackexchange.com/questions/24411/…). \$\endgroup\$
    – hyper-neutrino
    Feb 5 at 5:51
2
\$\begingroup\$

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!

\$\endgroup\$
1
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ You can do just R=range for 137 bytes: Try it online! \$\endgroup\$
    – AnttiP
    Feb 13 at 15:59
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Do this work? \$\endgroup\$
    – l4m2
    Jan 31 at 10:49
  • \$\begingroup\$ That's a great python 2 answer. \$\endgroup\$
    – solid.py
    Jan 31 at 18:06
1
\$\begingroup\$

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
      +    -       Addition
                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 Ƙ

\$\endgroup\$
1
\$\begingroup\$

Ruby, 83 78 bytes

->n{(2..n).select{|x|/^(!!+)\1+$/!~?!*x}.combination(3).find{|c,b,a|a*b+c==n}}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 31 at 21:57
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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);
}
\$\endgroup\$
1
\$\begingroup\$

80386 Machine Code, 110 107 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

\$\endgroup\$
1
  • \$\begingroup\$ Nice! And yes, a crashed program is a fair result. \$\endgroup\$
    – drmosley
    Mar 2 at 22:30
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
0
\$\begingroup\$

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.

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

05AB1E, 10 bytes

ÅP3.Æʒ`*+Q

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

Try it online or verify all test cases.

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)
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 39 bytes

NθIΦE…²θ⟦ι÷θι﹪θι⟧∧⬤⊞OΦιμ¹‹λ§ιμ⬤ι⬤…²λ﹪λν

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.

Nθ                                      Input as an integer
     …                                  Range from
      ²                                 Literal integer `2`
       θ                                To input integer
    E                                   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
                   ⊞O                  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
  I                                         Cast to string
                                            Implicitly print
\$\endgroup\$
0
\$\begingroup\$

BQN, 37 bytesSBCS

Main idea taken from l4m2's answer.

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

Run online!

\$\endgroup\$
0
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

Japt, 16 bytes

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

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

Try it

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.