Project Euler

Pages: 123
cran (218)
I made a bignums (well, lameints) maybe I can test them on this...
closed account (D80DSL3A)
The problems look cool. @craniumonempty Glad you took a crack at the BigNum challenge.
I got:

2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361
22493198378815695858127594672917553146825187145285692314043598457757469857480393
45677748242309854210746050623711418779541821530464749835819412673987675591655439
46077062914571196477686542167660429831652624386837205668069376

I'd have to write a special function to add the digits though...
Do you get this same value?
BTW I'd guess that the problem is meant to be solved without calculating 2^1000.
cran (218)
this is what I got... looks the same as yours, I think.. .hold up, I can just load and test them..

yep, they are equal, so there's a high prob that we are correct, or just lucky... lol, to be wrong with the same number. I'm pretty sure we aren't using the same way to get the number... did you just multiply to 1000, or did you do a binary type power function?


2**1000=10715086071862673209484250490600018105614048117055336074437503883703
5105112493612249319837881569585812759467291755314682518714528569231404359845
7757469857480393456777482423098542107460506237114187795418215304647498358194
1267398767559165543946077062914571196477686542167660429831652624386837205668
069376


edit... it cut some numbers on me
Last edited on
closed account (D80DSL3A)
Quick reply before work...
Our methods are likely different so the number is probably correct.
I used a simple for loop (multiply to 1000)

1
2
3
4
5
6
7
8
9
 
int main()
{
	BigInt z("2");
	for(int j=2; j<=1000; j++)
		z = z*2;
	z.to_string();// outputs result to console

	return 0;
}
cran (218)
yeah, I used a non-recursive binary function to multiply,,, much less multiplications.

note: i found out that code::blocks is more picky than g++ underneath it, so had to change a lot of stuff in lameints... either way...

Here's the function I wrote for Lameints:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/*
 * Original Author: Joseph B. Lamer
 * Lame Binary Power Function (nonrecursive) with LameInt
 */
void LameInt::z_powerBin( const LameInt &num )
{
	// sub 1, because we start with the number, if it's 1 (1-1=0), we are done...
	LameInt lognum = ( LameInt((LAMEINT_uint32)1) << num.log2().subAssign((LAMEINT_uint32)1) );
	if ( lognum > 0 ) {
		LameInt hold(*this);
		while ( lognum > 0 ) {
			this->multAssign(*this);
			if ( (num&lognum) ) {
				this->multAssign(hold);
			}
			lognum >>= 1;
		}
	}
}


let me know if I should explain it...
cran (218)
crap... I'm going to explain it anyway, because I like to hear myself type...

say we have 2**100

100 in binary is 1100100

with the log2 function (not sure if I actually wrote it correctly, but it works for me) we get

1000000

actually lets write the binary 100 like this

1
1
0
0
1
0
0

the first 1 will just be the number itself, using x as a var, and n = the number

x = n;

now we go down the line and we multiply by itself... if there is a 1 we also multipy the number again

1 x = n; x = n;
1 x *= x; x *= n; x = n**3
0 x *= x; x = n**6
0 x *= x; x = n**12
1 x *= x; x *= n; x = x**25
0 x *= x; x = x**50
0 x *= x; x = x**100
cran (218)
reading over it.. yeah, log 2 should be the representation of the power, not the next power down... since I'm working with int's it should return something like 6 for the binary number 1000000 (64 in decimal) since that's really the log2 of that... so log2 of 100 as an int should be 6 not 64... well, I'll have to change the name of the function
cran (218)
lol, I think I do return a 6.. can't remember anything... I guess I'll need to start commenting my own code a little better...
Browni3141 (578)
fun2code said:
BTW I'd guess that the problem is meant to be solved without calculating 2^1000.

I think it would be extremely difficult to do without calculating, if not impossible. Since I've been having trouble getting bignum libs to work, I just used arrays and a simple mutliplication algorithm. I like this method because it makes finding the digital sum trivial.
Duthomhas (13282)
Ah, problem 16. http://projecteuler.net/index.php?section=problems&id=16

This kind of problem is ridiculously simple in Tcl:
In Tcl:
 
 
puts [expr [join [split [expr 2**1000] {}] +]]

That's because Tcl has native bignums, and some powerful list operations.

   expr 2**1000 calculate 21000

   split ... {} split the number into a list of individual digits

   join ... + concatenate the elements of the list into a big addition problem

   expr ... evaluate the addition

   puts ... (display the result)

:-)
wolfgang (381)
What C++ needs is some native bignums. I sure it would be ridiculous to implement a cross platform version but it would be nice. I'm strill trying to wrap my brain around installing the GMP on Windows MinGW without the need of MSYS or Cygwin.
closed account (D80DSL3A)
@Browni3141
I admit I can't think of a way to solve the problem without finding 21000.
I was thinking of this problem when I said that:

Find the # of zeros ending 100 factorial.

Answer = # of factors of 5 present in the product = 100/5 + 100/25 = 24.

Also, an array and a simple multiplication algorithm is all I used in my own BigInt class, so you are well on your way just with that.

EDIT: @craniumonempty. Nice algorithm. I haven't done much with binary operations like bit shifting, etc. so I only partially understand your method. Evidently it works.
Last edited on
cran (218)
fun2code... yeah, I was going to explain it showing every detail and dropped that to just show what you do and when... as to why, let's get 2^8

1 -- x = 2^1 = 2, which is why we start with the number
0 -- x = x^2 = 2^2 = 4
0 -- x = x^2 = (2^2)^2 = 2^4 = 16
0 -- x = x^2 = ((2^2)^2)^2 = (2^4)^2 = 2^8 = 32

you are using the powers to decide when to multiply for that, it's not the quickest, but I think the quicker way was proven NP-complete, there are methods to speed it up though... This is by far the simplest to implement


as far as the Euler problem... I didn't even read the question and didn't realize that we were getting the sum of digits... this has to do with power modulus or something there about... I have to study it a bit more, but you are trying to find it with a Euler method, so it can be done even by hand...

something like

(2^4)^250 % 10 = 2^4 % 10 ( because 4 is the Euler Totient of 10 or something like that)

please, don't quote me, because I'm rusty on this... I'll have to study and figure out the method, before i shoot myself in the foot with misinformation again... Either way, I guarantee that's what they are looking for (since they call themselves "Project Euler"), not for you to calculate 2^1000 first and add the digits...

-- edit: I said guarantee that's what they are looking for, but they just want the answer from what I've read, but they "probably"want you to get it using something of Euler's
Last edited on
rapidcoder (1010)
Scala version is also very short, similar to Tcl:
 
 
println(BigInt(2).pow(1000).toString.map(_.toInt).sum)

Last edited on
Kyon (912)
"Very" unreadable too.
rapidcoder (1010)
I can't see anything unreadable, neither in the Tcl nor Scala code. Even though I do not know Tcl, I can understand how that code works, without looking into the documentation. It would be of course more readable if I wrote:

 
 
println((2 ** 1000).digits.sum)


It would require adding a new operator ** to the Int class and a new method digits to the BigInt class. Ability to add things to existing library classes is a nice feature. Ruby has it too, so I presume in Ruby the code would look almost the same.
Last edited on
Alrededor (166)
I'm with Albatross on this one. Tempted, but I probably have too many other projects to work on. Still ...

My BigInt class used binary as its native format so I was forced to implement conversion functions to and from binary, hex and decimal for my constructors and output operator. Here is a short program for the sum of the digits of 21000:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include "BigInt.h"
#include <string>
#include <numeric>

using std::string;
using std::cout;
using std::endl;

int main()
{
    string s = BigInt::binToDec( "1" + string( 1000, '0' ) );
    cout << accumulate( s.begin(), s.end(), 0L ) - 48 * s.size() << endl;
    return 0;
}


and here is a REXX program:

1
2
3
4
5
6
7
8
9
10
11
12
 
/* Project Euler 016 */

NUMERIC DIGITS 350
s = 2**1000
sum = 0
do until s = ""
  parse var s addend 2 s
  sum = sum + addend
end
say sum 

exit 0


The parse var s addend 2 s line parses the variable s putting everything up to position 2 ( but not including 2 into addend and the remainder into s.

I use to fool around quite a bit with REXX a few years ago when I was running OS/2 and since I had one program that I still wanted to run I picked up a copy of the Windows version went I started running Windows XP. REXX can do variable precision arithmetic and there are no conversion problems since everything is stored as a string and as long as a variable can be interpreted as a number you can use the arithmetic operators with it.
Duthomhas (13282)
For Problem 16 using a full bignum support library is overkill. Roll your own! :-)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
/* 016.cpp

   Project Euler -- Problem 16

   Copyright (c) 2011 Michael Thomas Greer
   Distributed under the Boost Software License, Version 1.0.
   (See http://www.boost.org/LICENSE_1_0.txt )

  +------------------------------------------------------------------------+
  | 2^(15) = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.    |
  |                                                                        |
  | What is the sum of the digits of the number 2^(1000)?                  |
  +------------------------------------------------------------------------+

*/

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
using namespace std;

typedef vector <char> bignum;

char carry( char curr, char prev )
  {
  return curr + (prev / 10);
  }

bignum& operator *= ( bignum& n, char k )  // k == single digit: 0..9
  {
  transform(           n.begin(), n.end(), n.begin(), bind2nd( multiplies <char> (),  k ) );
  if (n.back() > 9)
    n.push_back( 0 );
  adjacent_difference( n.begin(), n.end(), n.begin(), ptr_fun( &carry )                   );
  transform(           n.begin(), n.end(), n.begin(), bind2nd( modulus    <char> (), 10 ) );
  return n;
  }

int main()
  {
  bignum n;

  // Calculate 2**1000
  n.push_back( 2 );
  for (unsigned cntr = 1; cntr < 1000; cntr++)
    n *= 2;

  // Get the sum of the digits
  size_t sum_of_digits = accumulate( n.begin(), n.end(), (size_t)0 );

  // Turn the number into something that can be displayed...
  transform( n.begin(), n.end(), n.begin(), bind2nd( plus <char> (), '0' ) );
  // ...and display the results
  cout << "2**1000 is ";
  copy( n.rbegin(), n.rend(), ostream_iterator <char> ( cout, "" ) );
  cout << "\nThe sum of the digits is " << sum_of_digits << "\n";

  return 0;
  }

// end 016.cpp

[edit] Oops! Fixed typo!
Last edited on
Browni3141 (578)
Almost all of the problems are intended to be done without needing bignums. Using Duas' version is sufficient for all problems.
BTW, if you're a math geek like me then check out 144 and 309. 309 is surprisingly difficult but very rewarding if you find the formula.
m4ster r0shi (2201)
How did/would you solve this one? -> http://projecteuler.net/index.php?section=problems&id=81
Last edited on
Pages: 123