Project Euler Problem 12 (PHP)

Posted on October 10, 2011 by

Problem 12
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Script

Execution Time: 24.6897 seconds

require_once 'functions.php';

function getTriangle($n)
{
    $a = range(0, $n);
    return array_sum($a);
}

function addOne($n)
{
    return ++$n;
}

function getArrayProduct($a)
{
    $b = 1;
    foreach($a as $v) {
        $b *= $v;
    }

    return $b;
}

$maxDiv = 500;

$x = 1;

do {
    $x++;

    $t = getTriangle($x);
    $xa = new primefactor($t);

    $c = getArrayProduct(array_map('addOne', array_count_values($xa->factor)));
} while ($c < $maxDiv);

echo $t.PHP_EOL;
Posted in PHP, Programming, Project Euler | Tagged , , , | Leave a comment

Project Euler Problem 11 (PHP)

Posted on October 10, 2011 by

Problem 11
In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

Script

Execution Time: 0.0042 seconds

  4 $s = array();
$r = array();

$r[] = explode(' ', '08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08');
$r[] = explode(' ', '49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00');
$r[] = explode(' ', '81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65');
$r[] = explode(' ', '52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91');
$r[] = explode(' ', '22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80');
$r[] = explode(' ', '24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50');
$r[] = explode(' ', '32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70');
$r[] = explode(' ', '67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21');
$r[] = explode(' ', '24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72');
$r[] = explode(' ', '21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95');
$r[] = explode(' ', '78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92');
$r[] = explode(' ', '16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57');
$r[] = explode(' ', '86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58');
$r[] = explode(' ', '19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40');
$r[] = explode(' ', '04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66');
$r[] = explode(' ', '88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69');
$r[] = explode(' ', '04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36');
$r[] = explode(' ', '20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16');
$r[] = explode(' ', '20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54');
$r[] = explode(' ', '01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48');

foreach ($r as $q) {
    $c = count($q);
    for ($x=0; $x<$c-3; $x++) {
        $p = intval($q[$x])*intval($q[$x+1])*intval($q[$x+2])*intval($q[$x+3]);
        $s[] = $p;
    }
}

for ($x=0; $x<20; $x++) {
    for ($y=0; $y<17; $y++) {
        $p = intval($r[$y][$x])*intval($r[$y+1][$x])*intval($r[$y+2][$x])*intval($r[$y+3][$x]);
        $s[] = $p;
    }
}

for ($x=0; $x<17; $x++) {
    for ($y=0; $y<17; $y++) {
        $p = intval($r[$x][$y])*intval($r[$x+1][$y+1])*intval($r[$x+2][$y+2])*intval($r[$x+3][$y+3]);
        $s[] = $p;
    }
}

for ($x=20; $x>2; $x--) {
    for ($y=0; $y<17; $y++) {
        $p = intval($r[$x][$y])*intval($r[$x-1][$y+1])*intval($r[$x-2][$y+2])*intval($r[$x-3][$y+3]);
        $s[] = $p;
    }
}

rsort($s);
echo $s[0].PHP_EOL;
Posted in PHP, Programming, Project Euler | Tagged , , , | Leave a comment

Project Euler Problem 10 (PHP)

Posted on August 18, 2011 by

Problem 10
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Script

Execution Time: 88.6965 seconds

function isPrime($n)
{
    for ($x=2; $x<=sqrt($n); $x++) {
        if ($n%$x == 0) {
            return false;
        }
    }

    return true;
}

$maxNum = 2000000;
$sum = 2+3+5+7;

for ($x = 11; $x < $maxNum; $x=$x+2) {
    if ($x % 1000 == 1) echo $x.PHP_EOL;
    if ($x&5 > 0 && isPrime($x)) {
        $sum += $x;
    }
}

echo $sum.PHP_EOL;
Posted in PHP, Programming, Project Euler | Tagged , , , | Leave a comment

Project Euler Problem 9 (PHP)

Posted on August 18, 2011 by

Problem 9
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Script

Execution Time: 17.3896 seconds

$addTotal = 1000;

for ($x=1; $x<$addTotal; $x++) {
    for ($y=$x+1; $y<$addTotal; $y++) {
        for ($z=$y+1; $z<=$addTotal; $z++) {
            if (($x+$y+$z == $addTotal) && (($x*$x)+($y*$y) == ($z*$z))) {
                echo ($x*$y*$z).PHP_EOL;
                break 3;
            }
        }
    }
}
Posted in PHP, Programming, Project Euler | Tagged , , , | Leave a comment

Education and standardized testing

Posted on August 16, 2011 by

While looking through Hacker News this morning, I came across an article about the education system in China.  The article looks at the lives of four students within the system and weighs the pros and cons of how things are done at school.

I don’t know much about the education system in China, but there was a paragraph that really struck home with me.

Zhang Xiaolu, a teacher and gaokao grader in Nanjing, adds, “A lot of teachers tell students after they graduate from high school: ‘Please forget everything you have just learned.’ Because the teachers know that what they have taught is useless. A standardized test means standardized thought. I tell students, ‘It stuffs your heads so that you have no time to think about other things.’ This is the policy of keeping people in ignorance.”

I feel exactly the same way.  Standardized testing is pointless.  The kids don’t learn, and then when they are required to know something and apply it to life, they are unable to.  That alone is one of the primary reasons I support homeschooling and why my kids will always be home schooled as long as the situation continues to allow them to be.

Teaching to the test is ridiculous, pointless, and downright dumb.  Yes, there need to be ways to measure how schools are doing, but basing compensation on the results of standardized test only encourages the teachers to teach only what is needed to pass the test itself.

Growing up, we had standardized test.  And we spent the week before the test learning what would be expected of us.  The rest of the time was spent learning things that would be useful in real life.  I do not remember anything that was on the tests.  What I do remember are lessons I learned and experiences I had.  I fully plan to pass those opportunities on to my children so that they can grow in their ability to learn as well.

Posted in Education, Family, Home School, Personal, Public School | Tagged , , | Leave a comment

Running a Cub Scout pack.

Posted on August 15, 2011 by

As the Cubmaster of a Cub Pack, I am responsible along with the Assistant Cubmaster and the Pack Committee to deliver a quality program for the boys.  As part of that job, we need to have trained leaders to run the various dens and programs needed for successful development of the boys.  In a typical pack, those leaders come as a result of parent volunteers.  However, as leader of an LDS Pack, the recruitment of leaders is quite different.

The LDS church works off pure volunteerism.  The church leaders ask each individual to fill a specific roll within the congregation.  Some positions require a fair amount of work (such as the leader of a group — Primary President, etc.).  Others require only some work and typically only on specific days (a teacher only teaches on Sunday even though they may prepare on other days).  Included in those positions are the leaders of the Scouting program (both Boy Scouts and Cub Scouts).

In the Cub Scout program, we are required to have the following positions filled:

  • Cubmaster
  • Committee Chair
  • Committe Member (at least 1)
  • Webelos Den Leader
  • Pack Den Leader

The following are highly recommended positions to have filled:

  • Assistant Cubmaster
  • Assistant Webelos Den Leader
  • Assistant Pack Den Leader

And lest we forget the following positions that make life even easier (splitting the Pack Den Leader position):

  • Bear Den Leader
  • Assistant Bear Den Leader
  • Wolf Den Leader
  • Assistant Wolf Den Leader

Because of the differences between the Wolf/Bear and Webelos programs, they really need to be run separately.  Add to that the BSA requirements of two-deep leadership, and the highly recommended positions suddenly become required.  As a result, there are a total of 8 positions that need to be filled.  At the end of the school year last year, we had all roles filled.  Between then and now, the Webelos Den Leader and the Assistant Pack Den Leader have moved away.  Additionally, the Pack Den Leader has had some conflicts come up that will prevent him from being able to run the den.

That leaves us down by 3.  Add into that that the Committee chair is only in that position by name only.  We are left with Cubmaster, Assistant Cubmaster, Assistant Webelos Den Leader, and Committee Members.  Add in a Cub Scout with special needs that requires 1 on 1 assistance from one of the positions, and there are nowhere near enough people to run the program.

As an LDS pack, we require the leaders of the congregation to supply us with leaders.  They are the ones that ask the members to be a leader in the Cub Scout program.

But how do you handle it when the leaders refuse to ask people and the parents refuse to volunteer?  We don’t want to shut the pack down, but we don’t have the manpower to run it.  It is a frustrating position to be in.  Hopefully we will make ti through without too much scarring.

After all, the Cub Scout motto is: “Do Your Best”.

Posted in Cub Scouts, Personal | Tagged , | Leave a comment