## Triangle Numbers are a B!*\$@

This is the place for ALL of the user submitted challenges. If you create a little challenge/mission/riddle/whatever, post it here.
Forum rules
Do not post missions that you did NOT create without proper citing.

### Triangle Numbers are a B!*\$@

This is part of the continuous programming challenges!

The challenge:
Level: Harder

I have been debating on creating a nice mathematical programming challenge for a bit now, and I have come up with what I think will be a decent challenge. Here is what you will be using/doing.

The Triangle Function:
n(n+1)/2 or 1+2+...+n
Example of the Triangle Function if n = 4:
4(4+1)/2 = 10
1+2+3+4 = 10

The challenge:
Think of a clever way to find the product of the sum of all triangle numbers up to triangle numbers: 9, then 99, then 999, then 9999, etc ..., finally 99999999999999999999

For example, to find the sum of all triangle numbers up to triangle number 9, we do the following:
1(1+1)/2 + 2(2+1)/2 + 3(3+1)/2 + 4(4+1)/2 + 5(5+1)/2 + 6(6+1)/2 + 7(7+1)/2 + 8(8+1)/2 + 9(9+1)/2 = 165

You need write a program to get the sum as shown above for triangle numbers: 9, 99, 999, 9999, ..., 99999999999999999999, then add all the sums together for the final product. This will be your answer.

Points: 200

----

I don't want to spoil the clever thinkers out there so I will hold off on posting my answer. Congratz to whoever gets this challenge done correctly first, you may receive additional points.
Last edited by -Ninjex- on Fri Aug 16, 2013 4:53 pm, edited 2 times in total. For those that know
K: 0x2CD8D4F9 -Ninjex-
Moderator Posts: 1691
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

I don't suppose this will involve some kind of recursive algorythm? though dealing with such numbers will probably break the stack
Goatboy wrote:Oh, that's simple. All you need to do is dedicate many years of your life to studying security.

IF you feel like exchanging ASCII arrays, let me know Can you say brainwashing It's a non stop disco pretentious Posts: 1203
Joined: Wed Mar 03, 2010 12:48 am
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

pretentious wrote:I don't suppose this will involve some kind of recursive algorythm? though dealing with such numbers will probably break the stack

Correct you are. The goal is to think cleverly about how to get this to work. It's not impossible, I promise Also, yes dealing with those large numbers would take you a loooong time, plus it would indeed break the stack. For those that know
K: 0x2CD8D4F9 -Ninjex-
Moderator Posts: 1691
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

This was pretty trivial.

Code: Select all
`5050505050505050504994949494949494949495`

Tell me it's right and give me my pointz jgr
New User Posts: 4
Joined: Wed Nov 14, 2012 3:01 am
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

jgr wrote:This was pretty trivial.

Code: Select all
`5050505050505050504994949494949494949495`

Tell me it's right and give me my pointz

Remember you need to get the sum of the triangles 1-9, then 1-99, then 1-999, etc up to 1-99999999999999999999, add the sum of all of the above numbers together for your answer.

Also, if you read the rules it says to make a program to find the value. Do not just post a solution  For those that know
K: 0x2CD8D4F9 -Ninjex-
Moderator Posts: 1691
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

Code: Select all
`#include <stdlib.h>#include <stdio.h>#include <gmp.h>int main (void){   int i;   mpz_t n;   mpz_t total;   mpz_t tmp;   mpz_t sum;   mpz_init(n);   mpz_init(total);   mpz_init(tmp);   mpz_init(sum);   mpz_set_ui(n, 9);   mpz_set_ui(total, 0);   for (i = 0; i < 20; i++) {      // (n(n+1)(n+2)) / 6      mpz_add_ui(tmp, n, 1);      mpz_mul(sum, n, tmp);      mpz_add_ui(tmp, n, 2);      mpz_mul(sum, sum, tmp);      mpz_div_ui(sum, sum, 6);      mpz_add(total, total, sum);      mpz_mul_ui(n, n, 10);      mpz_add_ui(n, n, 9);   }   gmp_printf("%Zd\n", total);   mpz_clear(n);   mpz_clear(total);   mpz_clear(tmp);   mpz_clear(sum);   exit(EXIT_SUCCESS);}`

166833500166833500166833500166833500166814981648314981648315

It's in C
Last edited by jgr on Fri Aug 16, 2013 9:44 am, edited 1 time in total. jgr
New User Posts: 4
Joined: Wed Nov 14, 2012 3:01 am
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

@jgr, great work. As promised, for being the first person to think of the clever way of completing this challenge, you get bonus points. +275
Last edited by -Ninjex- on Fri Aug 16, 2013 4:53 pm, edited 1 time in total. For those that know
K: 0x2CD8D4F9 -Ninjex-
Moderator Posts: 1691
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

Easy closed form for this recurrence relation. Of course, jgr steals my thunder.

Code: Select all
`main = print . sum . take 20 . map tetra . iterate ((+ 9) . (* 10)) \$ 9  where tetra n = (n * (n + 1) * (n + 2)) `div` 6` apples
New User Posts: 37
Joined: Sat Apr 12, 2008 8:30 pm
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

@apples, once you post the language, I can check the code out

The first two are programs I whipped up in Ruby. The second Ruby program will demonstrate how you can take advantage of patterns to solve this problem. The third and fourth programs are done in Haskell. The third can be run from ghci, while the fourth can be compiled as an executable

See output
Code: Select all
`#!/usr/bin/rubyprompt = "> "puts "Enter the number to iterate:"print promptnum = gets.chompputs "Enter amount of decimal places:"print promptplaces = gets.chomp.to_idef tri(n)  return (n*(n+1)*(n+2)/6)endvalue = 0while places > 0  number = ''  places.times { number += num }  n = number.to_i  value += tri(n)  places -= 1endputs "Answer:"puts value`

See output
Code: Select all
`#!/usr/bin/ruby# Find the product of the sum of all triangle numbers up to: 9..n, where n is the decimal value we specify i.e, 3 = 999, 4 = 9999puts "How many decimal places would you like to check:" # asking user for how many decimal places to get product ofprint "> " # setting a little promptplaces = gets.chomp.to_i # getting the decimal value to get product ofplaces_save = places # saving the decimal value, since we change it later (line: 26)def tri(places) # creating a function called tri with the paramater as the decimal value to check  sixes = '' # setting a null value where we will store additional 6's (This changes depending on the decimal value)  zeros = '' # setting a null value where we will store additional 0's (This changes depending on the decimal value)  if places > 1 # if the decimal place to check is greater than 1    places = places-1 # subtract one from that value    places.times { sixes += '66' } # for every decimal value add '66' to our sixes variable    places.times { zeros += '0' } # for every decimal value add a '0' to our zeros variable    return "16"+sixes+"5"+zeros # return the value for the product of the triangle numbers  elsif places == 1 # if the decimal place to check is equal to 1    return 165 # return 165 (This is the product of: 1(1+1)/2 through 9(9+1)/2)  end # end the ifend # end the functiontotal = 0 # initializing a variable which will hold our final productwhile places > 0 # while places is greater than 0  value = tri(places) # store the product of the current decimal place in a variable called value  total += value.to_i # have total equal that value converter to an integer, since the function returns it as a string  places -= 1 # subtract 1 from our places variableend # end the loop if places is no longer greater than 0puts "The total sum for %s digits, is: %s" % [places_save, total] # print the product of the sum of all triangle numbers up to our desired decimal position`

Code: Select all
`result = let get n = div (n*(n+1)*(n+2)) 6 in let arr = take 20 (iterate ((+9) . (*10)) 9) in sum[get x | x <- arr]`

Code: Select all
`get n = div (n*(n+1)*(n+2)) 6main = print (sum[get x | x <- arr]) where arr = take 20 (iterate ((+9) . (*10)) 9) ` For those that know
K: 0x2CD8D4F9 -Ninjex-
Moderator Posts: 1691
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)

### Re: Triangle Numbers are a B!*\$@

Python. This looks a LOT more complicated than it actually turned out to be.

*NOTE: For credit and disclosure purposes I used Ninjex's triangle formula ((n*(n+1)*(n+2))/6). I started with fewer lines of code and a different method but number size ended up being to large no matter how I broke it down.

Code: Select all
`num=raw_input('Enter last triangle to compute 1-')decplaces=len(str(num))solution=0while decplaces>0:    number=''    repeats=decplaces    while repeats>0:        number+=num        repeats-=1    n=int(number)    solution+=((n*(n+1)*(n+2))/6)    decplaces-=1print solution`
There are 10 types of people in the world. Those who understand binary and those who don't. Amazingred
Experienced User Posts: 74
Joined: Wed Jul 25, 2012 7:10 pm
Location: Wayyyyyy out there
Blog: View Blog (0)

Next