Triangular Dependencies

A triangular number is a number that is the sum of n natural numbers from 1 to n. For example 1 + 2 + 3 + 4 = 10 so 10 is a triangular number.

Given a positive integer (0 < n <= 10000) as input (can be taken as an integer, or as a string), return the smallest possible triangular number that can be added to the input to create another triangular number.

For example given input 26, adding 10 results in 36, which is also a triangular number. There are no triangular numbers smaller than 10 that can be added to 26 to create another triangular number, so 10 is the correct result in this case.

0 is a triangular number, therefore if the input is itself a triangular number, the output should be 0

Testcases

Cases are given in the format input -> output (resulting triangular number)

0     -> 0   (0)
4     -> 6   (10)
5     -> 1   (6)
7     -> 3   (10)
8     -> 28  (36)
10    -> 0   (10)
24    -> 21  (45)
25    -> 3   (28)
26    -> 10  (36)
34    -> 21  (55)
10000 -> 153 (10153)


Scoring

This is so fewest bytes in each language wins!

• Isn't it 26 -> 2? – Okx Jun 29 '17 at 10:29
• @Okx I made the same mistake, you need to find a triangular number to add to the current one to make another triangular number. – Martin Ender Jun 29 '17 at 10:31
• Related. (borderline duplicate) – Martin Ender Jun 29 '17 at 10:31

Java 8, 58 57 bytes

n->{int i=0,m=0;while(n!=0)n+=n<0?++i:--m;return-~i*i/2;}


Online test suite

Thanks to Dennis for a 1-byte saving.

• Now this is Java, golfed! :) – Olivier Grégoire Jun 29 '17 at 13:39
• @Computronium, order of operations is guaranteed by the Java Language Specification. Java deliberately avoids some of the weaknesses of C. – Peter Taylor Jun 29 '17 at 14:39
• @Computronium docs.oracle.com/javase/tutorial/java/nutsandbolts/… – JollyJoker Jun 29 '17 at 14:40
• return-~i*i/2; saves a byte. – Dennis Jun 30 '17 at 6:38
• @Okx Java is pass-by-value for primitive types and pass-by-reference for objects (including arrays). If you want to actually output in the same variable, you have to be in a pass-by-reference context (explicitly said in your link). The only way I see to pass-by-reference that could work is to pass an int[] instead of an int as argument. But that means dealing with arrays later on. This could work: x->{int i=0,m=0,n=x;while(n!=0)n+=n<0?++i:--m;x=-~i*i/2;}, but it's 63 bytes. – Olivier Grégoire Jun 30 '17 at 13:49

Java (OpenJDK 8), 1168987 86 bytes

n->{int m=0,a=n,b;for(;a-->0;)for(b=0;b<=n;)if(2*n+a*a+a==b*b+b++)m=a*a+a;return m/2;}


Try it online!

• Nice answer (as always..). Hadn't noticed there was already a Java answer when I posted mine.. Mine was initially shorter, but not anymore it seems. :) – Kevin Cruijssen Jun 29 '17 at 11:20
• Thanks! Yeah, my first answer was really redundant. I fixed it and made it more mathy, though more processor-greedy as well. I'll check yours in a sec! – Olivier Grégoire Jun 29 '17 at 11:24
• I still don't understand what is happening here. Why is it working? You are replacing m every time, so what's the point? – V. Courtois Jun 29 '17 at 13:53
• @V.Courtois The question asks for the smallest m. So I go from a down to 0. "but you're assigning maybe 100 times the same value a*a+a to m in the b-loop", yep, I don't need to do it 100 times, but I'm gaining bytes by not breaking the b-loop earlier. – Olivier Grégoire Jun 29 '17 at 13:55
• I see @OlivierGrégoire. So that's anti-efficient on purpose :D – V. Courtois Jun 29 '17 at 13:57

MATL, 13 12 bytes

1 byte removed using an idea (set intersection) from Emigna's 05AB1E answer

Q:qYstG-X&X<


Try it online!

Explanation

Let t(n) = 1 + 2 + ··· + n denote the n-th triangular number.

The code exploits the fact that, given n, the solution is upper-bounded by t(n-1). To see this, observe that t(n-1) + n equals t(n) and so it is a triangular number.

Consider input 8 as an example.

Q:q   % Input n implicitly. Push [0 1 2 ... n]
% STACK: [0 1 2 3 4 5 6 7 8]
Ys    % Cumulative sum
% STACK: [0 1 3 6 10 15 21 28 36]
t     % Duplicate
% STACK: [0 1 3 6 10 15 21 28 36], [0 1 3 6 10 15 21 28 36]
G-    % Subtract input, element-wise
% STACK: [0 1 3 6 10 15 21 28 36], [-8 -7 -5 -2  2  7 13 20 28]
X&    % Set intersection
% STACK: 28
X<    % Minimum of array (in case there are several solutions). Implicit display
% STACK: 28

• Can you remove the leading Q by your argument about boundedness? – Giuseppe Jan 10 '18 at 17:05
• @Giuseppe No, that fails for input 8. When the output equals the bound t(n-1), the code obtains it as t(n)-n. So t(n) is necessary. Thanks for the idea anyway! – Luis Mendo Jan 10 '18 at 17:14

Mathematica, 46 bytes

Min[Select[(d=Divisors[2#])-2#/d,OddQ]^2-1]/8&


Neim, 12 9 bytes

tS𝕊Λt𝕚)0𝕔


This takes too long to compute (but works given infinite time and memory), so in the link I only generate the first 143 triangular numbers - using £𝕖, which is enough to handle an input of 10,000, but not enough to time out.

Warning: this may not work in future versions. If so, substitute £ for 143

Explanation:

t                 Infinite list of triangular numbers
[ 𝕖]             Select the first  v  numbers
[£ ]                              143
S𝕊           Subtract the input from each element
Λ  )       Only keep elements that are
t𝕚          triangular
0𝕔     Get the value closest to 0 - prioritising the higher number if tie


Try it!

• How are the first 143 triangle numbers enough for any input between 0 and 10000? With the input 9998, the expected result is 3118753, which is way above the 143rd triangle number (which is 10296). – Olivier Grégoire Jun 29 '17 at 12:36
• @OlivierGrégoire because This takes too long to compute (but works given infinite time and memory) – Stephen Jun 29 '17 at 12:56
• Thank you @StepHen but that's not what I said. What I implied is that the sentence "the first 143 triangular numbers [are] enough to handle an input of 10,000" is wrong. I haven't done the maths, but I believe that you should need around 10000 (give or take) triangle numbers to handle the cases up to 10000. – Olivier Grégoire Jun 29 '17 at 13:01
• @OlivierGrégoire I stated that it is enough to handle an input of 10,000, but not any number less than it. Feel free to change £ to a higher number, such as 200. – Okx Jun 29 '17 at 14:23
• @Okx Okay, I didn't understand it like that when I first read, thank you for taking the time to explain :) – Olivier Grégoire Jun 29 '17 at 14:26

PHP, 45 bytes

for(;!$$t;t+=++i){argn+t}=~+t;echo~$$t;


Try it online!

Is the shorter variant of for(;!$r[$t];$t+=++$i)$r[$argn+$t]=~+$t;echo~$r[$t];

Expanded

for(;!$$t; # stop if a triangular number exists where input plus triangular number is a triangular number t+=++i) # make the next triangular number {argn+t}=~+t; # build variable 4,5,7,10,... for input 4 echo~$$t; # Output result


PHP, 53 bytes

for(;$d=$t<=>$n+$argn;)~$d?$n+=++$k:$t+=++$i;echo+$n;


Try it online!

Use the new spaceship operator in PHP 7

Expanded

for(;$d=$t<=>$n+$argn;) # stop if triangular number is equal to input plus triangular number
~$d ?$n+=++$k # raise additional triangular number :$t+=++$i; # raise triangular number sum echo+$n; # Output and cast variable to integer in case of zero


PHP, 55 bytes

for(;fmod(sqrt(8*($t+$argn)+1),2)!=1;)$t+=++$i;echo+$t;  Try it online! Java 8, 110102100 93 bytes n->{int r=0;for(;t(r)+t(n+r)<0;r++);return r;}int t(int n){for(int j=0;n>0;n-=++j);return n;}  -2 bytes thanks to @PeterTaylor. -7 bytes thanks to @JollyJoker. Explanation: Try it here. n->{ // Method with integer as parameter and return-type int r=0; // Result-integer (starting at 0) for(;t(r)+t(n+r)<0; // Loop as long as either r or n+r isn't a triangular number r++ // And increase r by 1 after every iteration ); // End of loop return r; // Return the result of the loop } // End of method int t(int n){ // Separate method with integer as parameter and return-type // This method will return 0 if the input is a triangular number for(int i=0;n>0;) // Loop as long as the input n is larger than 0 n-=++j; // Decrease n by j every iteration, after we've raised j by 1 // End of loop (implicit / single-line body) return n; // Return n, which is now either 0 or below 0 } // End of separated method  • Easiest to read of the Java solutions :) – JollyJoker Jun 29 '17 at 15:09 • @JollyJoker Maybe that's why it's the longest. ;) Or is it because of my added explanation? – Kevin Cruijssen Jun 29 '17 at 18:21 • Nah, I was thinking about the code. I probably spent 15 mins figuring out how Peter Taylor's solution works. Yours is clear even without the comments. – JollyJoker Jun 30 '17 at 7:29 Brachylog, 17 15 bytes ⟦{a₀+}ᶠ⊇Ċ-ṅ?∧Ċh  Try it online! Explanation ⟦ [0, …, Input] { }ᶠ Find all… a₀+ …Sums of prefixes (i.e. triangular numbers) ⊇Ċ Take an ordered subset of two elements -ṅ? Subtracting those elements results in -(Input) ∧Ċh Output is the first element of that subset  Python 2, 59 bytes lambda n:min((r-2*n/r)**2/8for r in range(1,2*n,2)if n%r<1)  Try it online! This uses the following characterization of the triangular numbers t than can be added to n to get a triangular number: 8*t+1 = (r-2*s)^2 for divisor pairs (r,s) with r*s==n and r odd. The code takes the minimum of all such triangular numbers. Jelly, 8 bytes 0r+\ðf_Ḣ  Try it online! How it works 0r+\ðf_Ḣ Main link. Argument: n 0r Build [0, ..., n]. +\ Take the cumulative sum, generating A := [T(0), ..., T(n)]. ð Begin a dyadic chain with left argument A and right argument n. _ Compute A - n, i.e., subtract n from each number in A. f Filter; keep only numbers of A that appear in A - n. Ḣ Head; take the first result.  Japt, 242316 15 bytes ò å+ m!nNg)æ!øU  Test it 1 byte saved thanks to ETH Explanation  :Implicit input of integer U. ò :Create an array of integers from 0 to U, inclusive. å+ :Cumulatively reduce by summing. Result is implicitly assigned to variable V. m :Map over U. !n :From the current element subtract... Ng : The first element in the array of inputs (the original value of U). æ :Get the first element that returns true when... !øU : Checking if U contains it. :Implicit output of resulting integer.  • I think you can save a byte with æ!øV. Other than that, looks great :-) – ETHproductions Jun 30 '17 at 22:27 Octave, 38 36 bytes 2 bytes off thanks to @Giuseppe! @(n)(x=cumsum(0:n))(any(x+n==x'))(1)  Anonymous function that uses almost the same approach as my MATL answer. Try it online! 05AB1E, 12 bytes ÝηOãD€Æ¹QÏ¬¤  Uses the 05AB1E encoding. Try it online! Mathematica, 62 bytes (s=Min@Abs[m/.Solve[2#==(n-m)(n+m+1),{n,m},Integers]])(s+1)/2&  • I don't know Mathematica, but would Solve[2*#==m(m+1)-n(n+1) be shorter (if it works)? – Cows quack Jun 29 '17 at 10:43 • yes, I just posted my answer and trying to golf it right now – J42161217 Jun 29 '17 at 10:44 Python 2, 7871 70 bytes Seven bytes saved, thanx to ovs and theespinosa One more byte saved due to the remark of neil, x+9 is suffisant and checked for all natural numbers 0 <= n <= 10000. It was also verified for x+1 instead of x+9, it works also. x=input() I={n*-~n/2for n in range(x+1)} print min(I&{i-x for i in I})  Try it online! • You can use n*-~n/2 instead of n*(n+1)/2 – ovs Jun 29 '17 at 12:00 • Would range(x+9) work? – Neil Jun 29 '17 at 12:16 • You can use {n*(n+1)/2for n in range(999)} instead of explicit set and also use {} instead of set in the third line – TheEspinosa Jun 29 '17 at 12:52 JavaScript (ES6), 43 42 bytes f=(n,a=s=0)=>n?f(n+=n>0?--s:++a,a):a*++a/2 <input type=number min=0 value=0 oninput=o.textContent=f(+this.value)><pre id=o>0 Edit: Saved 1 byte thanks to @PeterTaylor. • Setting a global variable is a hideous abuse of a default parameter. +1. But FWIW you can save a further byte by replacing -++s with --s, as I did in my independently derived but quite similar Java version. (Addendum: you also need to change the test to n>0). – Peter Taylor Jun 29 '17 at 13:39 • @PeterTaylor Huh, so the n>s check was a red herring all along! – Neil Jun 29 '17 at 16:36 • Works not for 8192 – Jörg Hülsermann Jun 29 '17 at 19:24 • @JörgHülsermann If you're referring to the snippet, then your browser's stack size may not be large enough, or you may need a browser with experimental tail call optimisation. Alternatively, if you're using NodeJS for testing, use node --stack_size= to increase its stack size. – Neil Jun 29 '17 at 20:15 Python 3, 60 44 bytes f=lambda n,k=1:(8*n+1)**.5%1and f(n+k,k+1)+k  Thanks to @xnor for a suggestion that saved 16 bytes! Try it online! Background Let n be a non-negative integer. If n is the kth triangular number, we have which means there will be a natural solution if and only if 1 + 8n is an odd, perfect square. Clearly, checking the parity of 1 + 8n is not required. How it works The recursive function n accepts a single, non-negative integer as argument. When called with a single argument, k defaults to 1. First, (8*n+1)**.5%1 tests if n is a triangular number: if (and only if) it is, (8*n+1)**.5 will yield an integer, so the residue from the division by 1 will yield 0. If the modulus is 0, the and condition will fail, causing f to return 0. If this happens in the initial call to f, note that this is the correct output since n is already triangular. If the modulus is positive, the and condition holds and f(n+k,k+1)+k gets executed. This calls f again, incrementing n by k and k by 1, then adds k to the result. When f(n0, k0) finally returns 0, we back out of the recursion. The first argument in the first call was n, the second one n + 1, the third one n + 1 + 2, until finally n0 = n + 1 + … k0-1. Note that n0 - n is a triangular number. Likewise, all these integers will be added to the innermost return value (0), so the result of the intial call f(n) is n0 - n, as desired. • If you increment n in recursing as well, you can write n rather than (n+k). – xnor Jun 29 '17 at 17:07 • Or better, search triangular numbers directly. – xnor Jun 29 '17 at 17:19 • Wow, that's a lot nicer than what I was trying. – xnor Jun 29 '17 at 17:54 C# (.NET Core), 291 281 bytes class p{static int Main(string[]I){string d="0",s=I;int c=1,j,k;for(;;){j=k=0;string[]D=d.Split(' '),S=s.Split(' ');for(;j<D.Length;j++)for(;k<S.Length;k++)if(D[j]==S[k])return int.Parse(D[k]);j=int.Parse(D)+c++;d=d.Insert(0,$"{j} ");s=s.Insert(0,$"{j+int.Parse(I)} ");}}}  Try it online! Program that takes a string as input and outputs through Exit Code. Saved 10 Bytes thanks to Kevin Cruijssen • Hi, welcome to PPCG! You don't need a full program unless the challenge states otherwise. The default is program/function, so a lambda is allowed as well in C#. But if you want to use program, you can golf some things in your current code: class p{static int Main(string[]I){string d="0",s=I;int c=1,j,k;for(;;){j=k=0;string[]D=d.Split(' '),S=s.Split(' ');for(;j<D.Length;j++)for(;k<S.Length;k++)if(D[j]==S[k])return int.Parse(D[k]);j=int.Parse(D)+c++;d=d.Insert(0,$"{j} ");s=s.Insert(0,$"{j+int.Parse(I)} ");}}} (281 bytes) – Kevin Cruijssen Jun 30 '17 at 7:44 • @KevinCruijssen Thanks for the advice! using for(;;) to make an infinite loop is a nice bump, and I'll make sure to think more carefully about whether using var is actually more efficient than using an explicit type but combining the declarations, and I guess be more diligent in removing unnecessary brackets. As for the program vs. function, I started with a lambda but couldn't get it to run in TIO. I know a TIO link isn't actually necessary, but it's something I like to see in others' answers so I wanted at least something similar in my own. – Kamil Drakari Jun 30 '17 at 13:24 • I'm also not very good in C# lambdas tbh, I usually codegolf in Java. But I think this should be correct. (252 bytes). Also, in case you haven't seen it yet: Tips for code-golfing in C# and Tips for golfing in <all languages> might be interesting to read through. Again welcome, and +1 from me. Nice first answer. Enjoy your stay. :) – Kevin Cruijssen Jun 30 '17 at 13:45 JavaScript (ES7), 46 44 bytes f=(n,x=r=0)=>(8*(n+x)+1)**.5%1?f(n,x+=++r):x  Try it o.innerText=( f=(n,x=r=0)=>(8*(n+x)+1)**.5%1?f(n,x+=++r):x )(i.value=8);oninput=_=>o.innerText=f(+i.value) <input id=i type=number><pre id=o> • Would r=x=0 work? – Cows quack Jun 29 '17 at 11:07 • Sadly not, @KritixiLithos. – Shaggy Jun 29 '17 at 11:10 05AB1E, 8 bytes ÝηODI-Ãн  Try it online! or as a Test suite Explanation Ý # range [0 ... input] η # prefixes O # sum each D # duplicate I- # subtract input from each Ã # keep only the elements in the first list that also exist in the second list н # get the first (smallest)  Dyalog APL, 19 bytes 6 bytes saved thanks to @KritixiLithos {⊃o/⍨o∊⍨⍵+o←0,+\⍳⍵}  Try it online! How? o←0,+\⍳⍵ - assign o the first ⍵ triangular numbers o/⍨ - filter o by o∊⍨⍵+o - triangular numbers that summed with ⍵ produce triangulars ⊃ - and take the first • +\⍳⍵ should work instead of what you are using to generate the triangular numbers. – Cows quack Jun 29 '17 at 10:46 • I think ⊃ works instead of ⌊/ – Cows quack Jun 29 '17 at 10:58 Pari/GP, 54 bytes n->vecmin([y^2-1|y<-[2*n/d-d|d<-divisors(2*n)],y%2])/8  Try it online! Haskell, 56 bytes f x|e<-(elemscanl1(+)[0..x])=[n|n<-[0..],e n,e$x+n]!!0


Try it online!

L,RBFEREsECAAx$pBcB_B]VARBFEREsB]GEi$pGBcB*A8*1+.5^1%!!@A!@*b]EZBF#@


Try it online!, or see the test suite!

Even Java is beating me. I really need to add some set commands to Add++

How it works

L,    - Create a lambda function
- Example argument:  8
R   - Range;     STACK = [[1 2 3 4 5 6 7 8]]
BF  - Flatten;   STACK = [1 2 3 4 5 6 7 8]
ER  - Range;     STACK = [ [1 2] ... [1 2 3 4 5 6 7 8]
Es  - Sum;       STACK = [1 3 6 10 15 21 28 36]
EC  - Collect;   STACK = [[1 3 6 10 15 21 28 36]]
A   - Argument;  STACK = [[1 3 6 10 15 21 28 36] 8]
A   - Argument;  STACK = [[1 3 6 10 15 21 28 36] 8 8]
x   - Repeat;    STACK = [[1 3 6 10 15 21 28 36] 8 [8 8 8 8 8 8 8 8]]
$p - Remove; STACK = [[1 3 6 10 15 21 28 36] [8 8 8 8 8 8 8 8]] Bc - Zip; STACK = [[1 8] [3 8] [6 8] [10 8] [15 8] [21 8] [28 8] [36 8]] B_ - Deltas; STACK = [-7 -5 -2 2 7 13 20 28] B] - Wrap; STACK = [[-7 -5 -2 2 7 13 20 28]] V - Save; STACK = [] A - Argument; STACK =  R - Range; STACK = [[1 2 3 4 5 6 7 8]] BF - Flatten; STACK = [1 2 3 4 5 6 7 8] ER - Range; STACK = [ [1 2] ... [1 2 3 4 5 6 7 8]] Es - Sum; STACK = [1 3 6 10 15 21 28 36] B] - Wrap; STACK = [[1 3 6 10 15 21 28 36]] G - Retrieve; STACK = [[1 3 6 10 15 21 28 36] [-7 -5 -2 2 7 13 20 28]] Ei - Contains; STACK = [[1 3 6 10 15 21 28 36] [0 0 0 0 0 0 0 1]]$p  - Remove;    STACK = [[0 0 0 0 0 0 0 1]]
G   - Retrieve;  STACK = [[0 0 0 0 0 0 0 1] [-7 -5 -2 2 7 13 20 28]]
Bc  - Zip;       STACK = [[0 -7] [0 -5] [0 -2] [0 2] [0 7] [0 13] [0 20] [1 28]]
B*  - Products;  STACK = [0 0 0 0 0 0 0 28]
A   - Argument;  STACK = [0 0 0 0 0 0 0 28 8]
8*  - Times 8;   STACK = [0 0 0 0 0 0 0 28 64]
1+  - Increment; STACK = [0 0 0 0 0 0 0 28 65]
.5^ - Root;      STACK = [0 0 0 0 0 0 0 28 8.1]
1%  - Frac part; STACK = [0 0 0 0 0 0 0 28 0.1]
!!  - To bool;   STACK = [0 0 0 0 0 0 0 28 1]
@   - Reverse;   STACK = [1 28 0 0 0 0 0 0 0]
A   - Argument;  STACK = [1 28 0 0 0 0 0 0 0 8]
!   - Not;       STACK = [1 28 0 0 0 0 0 0 0 0]
@   - Reverse;   STACK = [0 0 0 0 0 0 0 0 28 1]
*   - Multiply;  STACK = [0 0 0 0 0 0 0 0 28]
b]  - Wrap;      STACK = [0 0 0 0 0 0 0 0 ]
EZ  - Unzero;    STACK = []
BF  - Flatten;   STACK = 
#   - Sort;      STACK = 
@   - Reverse;   STACK = 


R, 464443 41 bytes

function(x,y=cumsum(0:x))y[(x+y)%in%y]


Try it online!

An anonymous function with one mandatory argument, x; computes first x+1 triangular numbers as an optional argument to golf out a few curly braces. I used choose before I saw Luis Mendo's Octave answer.

I shaved off a few bytes of Luis Mendo's answer but forgot to use the same idea in my answer.

Jelly, 18 bytes

0rRS\$€ċ
0ð,+Ç€Ạð1#


Try it online!

Python 2, 83 81 bytes

• @Felipe Nardi Batista saved 2 bytes.
lambda n:min(x for x in i(n)if n+x in i(n))
i=lambda n:[i*-~i/2for i in range(n)]


Try it online!

APL (Dyalog Classic), 16 14 bytes

(⊃0∘,∩⊢-≢)+\∘⍳


Try it online!

Clojure, 74 bytes

#(nth(for[t[(reductions +(range))]i t :when((set(take 1e5 t))(+ i %))]i)0)
#(nth(for[R[reductions]i(R + %(range)):when((set(R - i(range 1e5)))0)]i)0)


Pick your favourite :) Loops might be shorter...

Python 2, 82 bytes

f=lambda n,R=:n-sum(R)and f(n,[R+[R[-1]+1],R[1:]][sum(R)>n])or sum(range(R))
`

Try it online

This was created by modifying this answer from the related question.

• works not for 8192 – Jörg Hülsermann Jun 29 '17 at 18:09
• It doesn't work for that on the related question either, because of the recursion depth. I'm not sure what the consensus is on that. – mbomb007 Jun 29 '17 at 19:26
• Some other answers have the same problem. I give only the info – Jörg Hülsermann Jun 29 '17 at 19:37