## 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: 1217
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_mul(sum, n, tmp);

mpz_mul(sum, sum, tmp);

mpz_div_ui(sum, sum, 6);

mpz_mul_ui(n, n, 10);
}

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/ruby
prompt = "> "
puts "Enter the number to iterate:"
print prompt
num = gets.chomp
puts "Enter amount of decimal places:"
print prompt
places = gets.chomp.to_i

def tri(n)
return (n*(n+1)*(n+2)/6)
end

value = 0
while places > 0
number = ''
places.times { number += num }
n = number.to_i
value += tri(n)
places -= 1
end
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 = 9999
puts "How many decimal places would you like to check:" # asking user for how many decimal places to get product of
print "> " # setting a little prompt
places = gets.chomp.to_i # getting the decimal value to get product of
places_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 if
end # end the function

total = 0 # initializing a variable which will hold our final product

while 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 variable
end # end the loop if places is no longer greater than 0

puts "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)) 6
main = 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=0
while decplaces>0:
number=''
repeats=decplaces
while repeats>0:
number+=num[0]
repeats-=1
n=int(number)
solution+=((n*(n+1)*(n+2))/6)
decplaces-=1
print 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