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!*$@

Post by -Ninjex- on Fri Aug 16, 2013 5:52 am
([msg=76879]see Triangle Numbers are a B!*$@[/msg])

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.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
^(-.^)>
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1457
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by pretentious on Fri Aug 16, 2013 7:27 am
([msg=76880]see Re: Triangle Numbers are a B!*$@[/msg])

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 ;)
pretentious wrote:Welcome to bat country
User avatar
pretentious
Contributor
Contributor
 
Posts: 687
Joined: Wed Mar 03, 2010 12:48 am
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by -Ninjex- on Fri Aug 16, 2013 7:43 am
([msg=76882]see Re: Triangle Numbers are a B!*$@[/msg])

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 :lol:
Also, yes dealing with those large numbers would take you a loooong time, plus it would indeed break the stack.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
^(-.^)>
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1457
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by jgr on Fri Aug 16, 2013 8:23 am
([msg=76884]see Re: Triangle Numbers are a B!*$@[/msg])

This was pretty trivial.

Code: Select all
5050505050505050504994949494949494949495


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


Re: Triangle Numbers are a B!*$@

Post by -Ninjex- on Fri Aug 16, 2013 8:51 am
([msg=76885]see Re: Triangle Numbers are a B!*$@[/msg])

jgr wrote:This was pretty trivial.

Code: Select all
5050505050505050504994949494949494949495


Tell me it's right and give me my pointz


Sorry, your answer is not correct.
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 :(
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
^(-.^)>
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1457
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by jgr on Fri Aug 16, 2013 9:39 am
([msg=76886]see Re: Triangle Numbers are a B!*$@[/msg])

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.
User avatar
jgr
New User
New User
 
Posts: 4
Joined: Wed Nov 14, 2012 3:01 am
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by -Ninjex- on Fri Aug 16, 2013 9:44 am
([msg=76887]see Re: Triangle Numbers are a B!*$@[/msg])

@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.
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
^(-.^)>
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1457
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by apples on Fri Aug 16, 2013 4:39 pm
([msg=76890]see Re: Triangle Numbers are a B!*$@[/msg])

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
User avatar
apples
New User
New User
 
Posts: 37
Joined: Sat Apr 12, 2008 8:30 pm
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by -Ninjex- on Fri Aug 16, 2013 4:54 pm
([msg=76891]see Re: Triangle Numbers are a B!*$@[/msg])

@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 "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 = 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)
If you're not willing to learn, no one can help you. If you're determined to learn, no one can stop you.⠠⠵
The absence of evidence is not evidence of absence.
I can explain it for you, but I can't understand it for you.
^(-.^)>
User avatar
-Ninjex-
Addict
Addict
 
Posts: 1457
Joined: Sun Sep 02, 2012 8:02 pm
Blog: View Blog (0)


Re: Triangle Numbers are a B!*$@

Post by Amazingred on Sat Sep 21, 2013 3:10 am
([msg=77445]see Re: Triangle Numbers are a B!*$@[/msg])

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.
User avatar
Amazingred
Experienced User
Experienced User
 
Posts: 73
Joined: Wed Jul 25, 2012 7:10 pm
Location: Wayyyyyy out there
Blog: View Blog (0)


Next

Return to User Submitted

Who is online

Users browsing this forum: No registered users and 0 guests