Fun With Numbers

[TigreLXIX]

DISCLAIMERS:

• The term "Fun" in the subject of this thread is highly subjective.  For instance, my wife rolls her eyes every time I talk about any of the topics I'm about to present.  Read at your own risk.
  
• This is going to be somewhat of a ramble.  I apologize, but I promise...there is a point to all of this.
  

A while back, I thought it would be neat to learn the mathematical constant Pi, one digit a day, for an entire year - so by the end of the year, I would have 365 digits memorized.  To make a long story short, I have a Pi trainer app and can punch in about 650 digits without making an error.  My ability to recite is probably somewhat less than that, because some of the memorization in using the Pi trainer is that "muscle memory" helps my fingers know which digit to select next.

There is a point in the random sequence of Pi, which starts at digit 762 (after the decimal place), with a series of 6 consecutive 9s.  This is known as the Feynman point, after some guy who thought it would be cool to learn Pi to this spot.

Since I want to be cool like Feynman, I wanted to find the next-closest sequence of 6 digits in a row.  I wasn't particular - I would've settled for 6 3s or 6 8s - but it turns out, the next such sequence is also 9s.  It is also over 193,000 digits deep - so I have abandoned this quest (considering the official world record for Pi memorization is only about 70,000 digits).

Anyway, as a result of my aforementioned quest, I found a site (http://angio.net/pi) where you can search for a string within the first 200 million (200,000,000) digits of Pi...which in turn led me to find the Project Euler website.  This site presents a bunch of fun (*see disclaimer) problems that can be solved using math and computer programming skills.  After discovering the site last night, I spent a few hours solving the first few problems, and stayed up way too late.  At any rate, so far I have been able to use Microsoft Excel to solve the first 9 problems (I have a macro running as I type which will help to solve problem 10), but I anticipate using some of my limited programming skills to solve some of the more challenging problems.  I think it will definitely enhance my problem-solving and computer programming skills.

Just thought I'd pass along, because I know there are a few others who are into math and computer programming. Enjoy!

[ToreadorElder]

Interesting. Might do several of these.

#10 is easy enough to code, just somewhat time-consuming if you use a brute-force approach. I know there's a pretty quick test for a number probably being prime, but I don't remember the details.

You should be able to use VBA for any of the problems I was looking at...some need some creative thinking. Problem 16:
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?

You just gotta think this one like a person...not a computer.

Fun indeed. Good brain games. Thanks.

[ToreadorElder]

Heh...some of the solutions are extremely lazy. Problem 10 is, find the sum of all prime numbers less than 2,000,000. One guy used Matlab...which has a built-in isprime() check. Come on, at least write that yourself!

[TigreLXIX]

(07-23-2016, 02:04 PM)ToreadorElder Wrote:  #10 is easy enough to code, just somewhat time-consuming if you use a brute-force approach.

I didn't see this when I first looked at the site, but the "About" page (which is also the main landing page) says

http://projecteuler.net Wrote:Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

I originally used a "brute force" approach to #10, and my macro ran for several hours (partly because my approach actually generated a list of prime numbers, from low to high - as opposed to using a "sieve" function to eliminate numbers that are not prime).  Now I'm trying to rewrite the VBA code to go the other way, which will streamline it more.

(07-23-2016, 04:10 PM)ToreadorElder Wrote:  Heh...some of the solutions are extremely lazy.  Problem 10 is, find the sum of all prime numbers less than 2,000,000.  One guy used Matlab...which has a built-in isprime() check.  Come on, at least write that yourself!

Yeah, what's the point of "solving" the problems if you don't do the work?  The point is to make you think creatively and learn techniques.

[ToreadorElder]

Well, VBA is in itself slow, and the sieve isn't all that fast.  This is mine:

private static TreeSet<Long> primes = new TreeSet<>();

private static void computePrimes(long n) {
// n is the upper bound for the set of primes
primes.clear();
primes.add(2L);
primes.add(3L);
primes.add(5L);
primes.add(7L);

for (long i=11; i<=n; i+=10) {
if (checkPrime(i))
primes.add(i);
if (checkPrime(i+2))
primes.add(i+2);
if (checkPrime(i+6))
primes.add(i+6);
if (checkPrime(i+8))
primes.add(i+8);
}
}

private static boolean checkPrime(long n) {

long lastPossible = (long) Math.sqrt(n);

for (long p : primes) {
if (n % p == 0)
return false;
else if (p > lastPossible)
return true;
}
return true;
}

NOTE:  I had to use the long data type to support 64 bits for problem 3.  Also note the great shortcut...the FIRST prime factor for a number cannot be larger than the square root of that number, or the number is prime.

The runtime on this...actually initializing the Java VM seems to be taking a fair bit of time, judging by even the super-simple and fast problems like #1.  But problem 4, which is finding the largest prime factor of a 12 digit number, and problem 10 took just a few seconds.

n % p is the modulo operator.  n % p == b when n = k*p + b, and  0<=b<n.  Or in other words, b is the remainder of n/p.  And it's computed very quickly...at worst, computationally, it's  n - (p * floor(n/p) ).

[TigreLXIX]

(07-23-2016, 06:01 PM)ToreadorElder Wrote:  Also note the great shortcut...the FIRST prime factor for a number cannot be larger than the square root of that number, or the number is prime.

Yes, I did read that when doing some research on the subject...and intuitively, it makes sense. I didn't include it in my macro, though. It probably would've helped it run a little faster if I had.

[ToreadorElder]

MUCH faster.  MUCH, MUCH faster.

For example:  say you're finding the largest prime below 4,000,000.  Nice easy square root there, 2000.  Number of primes < 2000:  303.  Number of primes < 4M:  283,146.

Not to mention that you have to find all the primes below 4,000,000...so building the list keeps needing more and more time.  If you don't stop at square root, the time to compute the prime numbers < n is an order(n^2) problem...and that's LONG.

Edit:  I'm skipping around.  I'll do the Collatz problem later.  Right now I'm doing one of the major 'curiousity' problems...#27.  It's baseball season...put a ball game on for a nice low level of distraction, and think.... :

[TigreLXIX]

(07-23-2016, 07:20 PM)ToreadorElder Wrote:  I'm skipping around.  I'll do the Collatz problem later.  Right now I'm doing one of the major 'curiousity' problems...#27.  It's baseball season...put a ball game on for a nice low level of distraction, and think.... :

I just looked at the Collatz problem...looks intriguing, but I need to get some sleep.

Speaking of baseball...you're a Padres fan, right? They're in about the same boat as my team (the Phillies) - although I think the Phils are a year or two ahead...nice group of young players there. I suppose if we want to get off on that tangent, we ought to start another thread though...maybe some other time.

[ToreadorElder]

Padres?  I root for major league teams...not AA teams.....  

I'm not close to any team, so there isn't any team I root for these days.  I'm technically in the home broadcast area for, IIRC, D'backs, Padres, and Rangers.  Maybe Rockies and Astros too.  Home broadcast areas are ridiculous, IMO.  So I can catch those broadcasts.  But these days, there's a LOT of games on MLB (daytime and evening), there's the 2 Saturday Fox games, and TBS has a Sunday game.  So it's whomever.

Break time here too.  1-10, 15, 16, and 27.  27 is VERY interesting to observe while you shake out the algorithms.  Enough for one afternoon and evening.  And 11 is just an ugly brute-force bounds-checking problem.  Dull.  Tomorrow, while the riders of the Tour lolligag in to Paris.

[rakbeater]

(07-23-2016, 11:22 PM)ToreadorElder Wrote:  Padres?  I root for major league teams...not AA teams.....  

HAHAHAHAHAHAHAHAHAHAHAHA  awesome.