Project Euler Problems
Project Euler Problems
Problem 1
=========
Answer: e1edf9d1967ca96767dcc2b2d6df69f4
Problem 2
=========
Answer: 4194eb91842c8e7e6df099ca73c38f28
Problem 3
=========
Answer: 94c4dd41f9dddce696557d3717d98d82
Problem 4
=========
A palindromic number reads the same both ways. The largest palindrome made
from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
Answer: d4cfc27d16ea72a96b83d9bdef6ce2ec
Problem 5
=========
2520 is the smallest number that can be divided by each of the numbers
from 1 to 10 without any remainder.
Answer: bc0d0a22a7a46212135ed0ba77d22f3a
Problem 6
=========
The sum of the squares of the first ten natural numbers is,
The square of the sum of the first ten natural numbers is,
Hence the difference between the sum of the squares of the first ten
natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one
hundred natural numbers and the square of the sum.
Answer: 867380888952c39a131fe1d832246ecc
Problem 7
=========
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
that the 6th prime is 13.
Answer: 8c32ab09ec0210af60d392e9b2009560
Problem 8
=========
The four adjacent digits in the 1000-digit number that have the greatest
product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
Find the thirteen adjacent digits in the 1000-digit number that have the
greatest product. What is the value of this product?
Answer: 0f53ea7949d32ef24f9186207600403c
Problem 9
=========
Answer: 24eaa9820350012ff678de47cb85b639
Problem 10
==========
Answer: d915b2a9ac8749a6b837404815f1ae25
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
Answer: 678f5d2e1eaa42f04fa53411b4f441ac
Problem 12
==========
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?
Answer: 8091de7d285989bbfa9a2f9f3bdcc7c0
Problem 13
==========
Work out the first ten digits of the sum of the following one-hundred
50-digit numbers.
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690
Answer: 361113f19fd302adc31268f8283a4f2d
Problem 14
==========
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following
sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
Answer: 5052c3765262bb2c6be537abd60b305e
Problem 15
==========
Starting in the top left corner of a 2×2 grid, and only being able to move
to the right and down, there are exactly 6 routes to the bottom right
corner.
p_015.gif
Answer: 928f3957168ac592c4215dcd04e0b678
Problem 16
==========
Problem 17
==========
If the numbers 1 to 5 are written out in words: one, two, three, four,
five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written
out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and
forty-two) contains 23 letters and 115 (one hundred and fifteen) contains
20 letters. The use of "and" when writing out numbers is in compliance
with British usage.
Answer: 6a979d4a9cf85135408529edc8a133d0
Problem 18
==========
3
7 4
2 4 6
8 5 9 3
Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NOTE: As there are only 16384 routes, it is possible to solve this problem
by trying every route. However, [1]Problem 67, is the same challenge with
a triangle containing one-hundred rows; it cannot be solved by brute
force, and requires a clever method! ;o)
Visible links
1. problem=67
Answer: 708f3cf8100d5e71834b1db77dfa15d6
Problem 19
==========
You are given the following information, but you may prefer to do some
research for yourself.
How many Sundays fell on the first of the month during the twentieth
century (1 Jan 1901 to 31 Dec 2000)?
Answer: a4a042cf4fd6bfb47701cbc8a1653ada
Problem 20
==========
n! means n × (n − 1) × ... × 3 × 2 × 1
Answer: 443cb001c138b2561a0d90720d6ce111
Problem 21
==========
Let d(n) be defined as the sum of proper divisors of n (numbers less than
n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair
and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22,
44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1,
2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.
Answer: 51e04cd4e55e7e415bf24de9e1b0f3ff
Problem 22
==========
For example, when the list is sorted into alphabetical order, COLIN, which
is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So,
COLIN would obtain a score of 938 × 53 = 49714.
Visible links
1. names.txt
Answer: f2c9c91cb025746f781fa4db8be3983f
Problem 23
==========
A perfect number is a number for which the sum of its proper divisors is
exactly equal to the number. For example, the sum of the proper divisors
of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect
number.
Find the sum of all the positive integers which cannot be written as the
sum of two abundant numbers.
Answer: 2c8258c0604152962f7787571511cf28
Problem 24
==========
Answer: 7f155b45cb3f0a6e518d59ec348bff84
Problem 25
==========
F[1] = 1
F[2] = 1
F[3] = 2
F[4] = 3
F[5] = 5
F[6] = 8
F[7] = 13
F[8] = 21
F[9] = 34
F[10] = 55
F[11] = 89
F[12] = 144
The 12th term, F[12], is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?
Answer: a376802c0811f1b9088828288eb0d3f0
Problem 26
==========
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can
be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which ^1/[d] contains the longest recurring
cycle in its decimal fraction part.
Answer: 6aab1270668d8cac7cef2566a1c5f569
Problem 27
==========
n² + n + 41
It turns out that the formula will produce 40 primes for the consecutive
values n = 0 to 39. However, when n = 40, 40^2 + 40 + 41 = 40(40 + 1) + 41
is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly
divisible by 41.
Answer: 69d9e3218fd7abb6ff453ea96505183d
Problem 28
==========
21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13
It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral
formed in the same way?
Answer: 0d53425bd7c5bf9919df3718c8e49fa6
Problem 29
==========
If they are then placed in numerical order, with any repeats removed, we
get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤
100 and 2 ≤ b ≤ 100?
Answer: 6f0ca67289d79eb35d19decbc0a08453
Problem 30
==========
Surprisingly there are only three numbers that can be written as the sum
of fourth powers of their digits:
Find the sum of all the numbers that can be written as the sum of fifth
powers of their digits.
Answer: 27a1779a8a8c323a307ac8a70bc4489d
Problem 31
==========
How many different ways can £2 be made using any number of coins?
Answer: 142dfe4a33d624d2b830a9257e96726d
Problem 32
==========
HINT: Some products can be obtained in more than one way so be sure to
only include it once in your sum.
Answer: 100f6e37d0b0564490a2ee27eff0660d
Problem 33
==========
There are exactly four non-trivial examples of this type of fraction, less
than one in value, and containing two digits in the numerator and
denominator.
Answer: f899139df5e1059396431415e770c6dd
Problem 34
==========
Answer: 60803ea798a0c0dfb7f36397d8d4d772
Problem 35
==========
The number, 197, is called a circular prime because all rotations of the
digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37,
71, 73, 79, and 97.
Answer: b53b3a3d6ab90ce0268229151c9bde11
Problem 36
==========
Find the sum of all numbers, less than one million, which are palindromic
in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include
leading zeros.)
Answer: 0e175dc2f28833885f62e7345addff03
Problem 37
==========
Find the sum of the only eleven primes that are both truncatable from left
to right and right to left.
Answer: cace46c61b00de1b60874936a093981d
Problem 38
==========
192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
Answer: f2a29ede8dc9fae7926dc7a4357ac25e
Problem 39
==========
Answer: fa83a11a198d5a7f0bf77a1987bcd006
Problem 40
==========
0.123456789101112131415161718192021...
If d[n] represents the n^th digit of the fractional part, find the value
of the following expression.
Answer: 6f3ef77ac0e3619e98159e9b6febf557
Problem 41
==========
Answer: d0a1bd6ab4229b2d0754be8923431404
Problem 42
==========
The n^th term of the sequence of triangle numbers is given by, t[n] =
½n(n+1); so the first ten triangle numbers are:
Visible links
1. words.txt
Answer: 82aa4b0af34c2313a562076992e50aa3
Problem 43
==========
Let d[1] be the 1^st digit, d[2] be the 2^nd digit, and so on. In this
way, we note the following:
• d[2]d[3]d[4]=406 is divisible by 2
• d[3]d[4]d[5]=063 is divisible by 3
• d[4]d[5]d[6]=635 is divisible by 5
• d[5]d[6]d[7]=357 is divisible by 7
• d[6]d[7]d[8]=572 is divisible by 11
• d[7]d[8]d[9]=728 is divisible by 13
• d[8]d[9]d[10]=289 is divisible by 17
Problem 44
==========
Find the pair of pentagonal numbers, P[j] and P[k], for which their sum
and difference are pentagonal and D = |P[k] − P[j]| is minimised; what is
the value of D?
Answer: 2c2556cb85621309ca647465ffa62370
Problem 45
==========
Find the next triangle number that is also pentagonal and hexagonal.
Answer: 30dfe3e3b286add9d12e493ca7be63fc
Problem 46
==========
It was proposed by Christian Goldbach that every odd composite number can
be written as the sum of a prime and twice a square.
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
Answer: 89abe98de6071178edb1b28901a8f459
Problem 47
==========
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
The first three consecutive numbers to have three distinct prime factors
are:
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime
factors. What is the first of these numbers?
Answer: 748f517ecdc29106e2738f88aa7530f4
Problem 48
==========
Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
Answer: 0829124724747ae1c65da8cae5263346
Problem 49
==========
The arithmetic sequence, 1487, 4817, 8147, in which each of the terms
increases by 3330, is unusual in two ways: (i) each of the three terms are
prime, and, (ii) each of the 4-digit numbers are permutations of one
another.
What 12-digit number do you form by concatenating the three terms in this
sequence?
Answer: 0b99933d3e2a9addccbb663d46cbb592
Problem 50
==========
The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below
one-hundred.
Which prime, below one-million, can be written as the sum of the most
consecutive primes?
Answer: 73229bab6c5dc1c7cf7a4fa123caf6bc
Problem 51
==========
By replacing the 1^st digit of the 2-digit number *3, it turns out that
six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all
prime.
By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this
5-digit number is the first example having seven primes among the ten
generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663,
56773, and 56993. Consequently 56003, being the first member of this
family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not
necessarily adjacent digits) with the same digit, is part of an eight
prime value family.
Answer: e2a8daa5eb919905dadd795593084c22
Problem 52
==========
It can be seen that the number, 125874, and its double, 251748, contain
exactly the same digits, but in a different order.
Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x,
contain the same digits.
Answer: a420384997c8a1a93d5a84046117c2aa
Problem 53
==========
There are exactly ten ways of selecting three from five, 12345:
123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
In general,
Answer: e3b21256183cf7c2c7a66be163579d37
Problem 54
==========
In the card game poker, a hand consists of five cards and are ranked, from
lowest to highest, in the following way:
If two players have the same ranked hands then the rank made up of the
highest value wins; for example, a pair of eights beats a pair of fives
(see example 1 below). But if two ranks tie, for example, both players
have a pair of queens, then highest cards in each hand are compared (see
example 4 below); if the highest cards tie then the next highest cards are
compared, and so on.
Visible links
1. poker.txt
Answer: 142949df56ea8ae0be8b5306971900a4
Problem 55
==========
Although no one has proved it yet, it is thought that some numbers, like
196, never produce a palindrome. A number that never forms a palindrome
through the reverse and add process is called a Lychrel number. Due to the
theoretical nature of these numbers, and for the purpose of this problem,
we shall assume that a number is Lychrel until proven otherwise. In
addition you are given that for every number below ten-thousand, it will
either (i) become a palindrome in less than fifty iterations, or, (ii) no
one, with all the computing power that exists, has managed so far to map
it to a palindrome. In fact, 10677 is the first number to be shown to
require over fifty iterations before producing a palindrome:
4668731596684224866951378664 (53 iterations, 28-digits).
Answer: 077e29b11be80ab57e1a2ecabb7da330
Problem 56
==========
Considering natural numbers of the form, a^b, where a, b < 100, what is
the maximum digital sum?
Answer: c22abfa379f38b5b0411bc11fa9bf92f
Problem 57
==========
The next three expansions are 99/70, 239/169, and 577/408, but the eighth
expansion, 1393/985, is the first example where the number of digits in
the numerator exceeds the number of digits in the denominator.
Answer: b3e3e393c77e35a4a3f3cbd1e429b5dc
Problem 58
==========
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49
It is interesting to note that the odd squares lie along the bottom right
diagonal, but what is more interesting is that 8 out of the 13 numbers
lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
If one complete new layer is wrapped around the spiral above, a square
spiral with side length 9 will be formed. If this process is continued,
what is the side length of the square spiral for which the ratio of primes
along both diagonals first falls below 10%?
Answer: b62fc92a2561538525c89be63f36bf7b
Problem 59
==========
For unbreakable encryption, the key is the same length as the plain text
message, and the key is made up of random bytes. The user would keep the
encrypted message and the encryption key in different locations, and
without both "halves", it is impossible to decrypt the message.
Your task has been made easy, as the encryption key consists of three
lower case characters. Using [1]cipher1.txt, a file containing the
encrypted ASCII codes, and the knowledge that the plain text must contain
common English words, decrypt the message and find the sum of the ASCII
values in the original text.
Visible links
1. cipher1.txt
Answer: 68f891fe214e2bfa07c998ad5d0a390f
Problem 60
==========
The primes 3, 7, 109, and 673, are quite remarkable. By taking any two
primes and concatenating them in any order the result will always be
prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The
sum of these four primes, 792, represents the lowest sum for a set of four
primes with this property.
Find the lowest sum for a set of five primes for which any two primes
concatenate to produce another prime.
Answer: a4b5a70ca8cf24d0eb4330748d1e72e5
Problem 61
==========
The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three
interesting properties.
1. The set is cyclic, in that the last two digits of each number is the
first two digits of the next number (including the last number with
the first).
2. Each polygonal type: triangle (P[3,127]=8128), square (P[4,91]=8281),
and pentagonal (P[5,44]=2882), is represented by a different number in
the set.
3. This is the only set of 4-digit numbers with this property.
Find the sum of the only ordered set of six cyclic 4-digit numbers for
which each polygonal type: triangle, square, pentagonal, hexagonal,
heptagonal, and octagonal, is represented by a different number in the
set.
Answer: caec17d84884addeec35c3610645ab63
Problem 62
==========
The cube, 41063625 (345^3), can be permuted to produce two other cubes:
56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallest
cube which has exactly three permutations of its digits which are also
cube.
Find the smallest cube for which exactly five permutations of its digits
are cube.
Answer: 8f46b522b5401b8b6df99a7410eea44b
Problem 63
==========
How many n-digit positive integers exist which are also an nth power?
Answer: f457c545a9ded88f18ecee47145a72c0
Problem 64
==========
All square roots are periodic when written as continued fractions and can
be written in the form:
√N = a[0] + 1
a[1] + 1
a[2] + 1
a[3] + ...
√23 = 4 + √23 — 4 = 4 + 1 = 4 + 1
1 1 + √23 – 3
√23—4 7
√23 = 4 + 1
1 + 1
3 + 1
1 + 1
8 + ...
It can be seen that the sequence is repeating. For conciseness, we use the
notation √23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats
indefinitely.
√2=[1;(2)], period=1
√3=[1;(1,2)], period=2
√5=[2;(4)], period=1
√6=[2;(2,4)], period=2
√7=[2;(1,1,1,4)], period=4
√8=[2;(1,4)], period=2
√10=[3;(6)], period=1
√11=[3;(3,6)], period=2
√12= [3;(2,6)], period=2
√13=[3;(1,1,1,1,6)], period=5
Answer: dc960c46c38bd16e953d97cdeefdbc68
Problem 65
==========
√2 = 1 + 1
2 + 1
2 + 1
2 + 1
2 + ...
1 + 1 = 3/2
2
1 + 1 = 7/5
2 + 1
2
1 + 1 = 17/12
2 + 1
2 + 1
2
1 + 1 = 41/29
2 + 1
2 + 1
2 + 1
2
Find the sum of digits in the numerator of the 100^th convergent of the
continued fraction for e.
Answer: 7a614fd06c325499f1680b9896beedeb
Problem 66
==========
x^2 – Dy^2 = 1
3^2 – 2×2^2 = 1
2^2 – 3×1^2 = 1
9^2 – 5×4^2 = 1
5^2 – 6×2^2 = 1
8^2 – 7×3^2 = 1
Find the value of D ≤ 1000 in minimal solutions of x for which the largest
value of x is obtained.
Answer: 3a066bda8c96b9478bb0512f0a43028c
Problem 67
==========
3
7 4
2 4 6
8 5 9 3
Find the maximum total from top to bottom in [1]triangle.txt, a 15K text
file containing a triangle with one-hundred rows.
Visible links
1. triangle.txt
2. problem=18
Answer: 9d702ffd99ad9c70ac37e506facc8c38
Problem 68
==========
Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6,
and each line adding to nine.
Working clockwise, and starting from the group of three with the
numerically lowest external node (4,3,2 in this example), each solution
can be described uniquely. For example, the above solution can be
described by the set: 4,3,2; 6,2,1; 5,1,3.
It is possible to complete the ring with four different totals: 9, 10, 11,
and 12. There are eight solutions in total.
p_068_1.gif
p_068_2.gif
Answer: 26227442c6fed0292a528ac3790175be
Problem 69
==========
┌────┬──────────────────┬──────┬───────────┐
│ n │ Relatively Prime │ φ(n) │ n/φ(n) │
├────┼──────────────────┼──────┼───────────┤
│ 2 │ 1 │ 1 │ 2 │
├────┼──────────────────┼──────┼───────────┤
│ 3 │ 1,2 │ 2 │ 1.5 │
├────┼──────────────────┼──────┼───────────┤
│ 4 │ 1,3 │ 2 │ 2 │
├────┼──────────────────┼──────┼───────────┤
│ 5 │ 1,2,3,4 │ 4 │ 1.25 │
├────┼──────────────────┼──────┼───────────┤
│ 6 │ 1,5 │ 2 │ 3 │
├────┼──────────────────┼──────┼───────────┤
│ 7 │ 1,2,3,4,5,6 │ 6 │ 1.1666... │
├────┼──────────────────┼──────┼───────────┤
│ 8 │ 1,3,5,7 │ 4 │ 2 │
├────┼──────────────────┼──────┼───────────┤
│ 9 │ 1,2,4,5,7,8 │ 6 │ 1.5 │
├────┼──────────────────┼──────┼───────────┤
│ 10 │ 1,3,7,9 │ 4 │ 2.5 │
└────┴──────────────────┴──────┴───────────┘
Answer: bf08b01ead83cbd62a9839ca1cf35ada
Problem 70
==========
Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n
and the ratio n/φ(n) produces a minimum.
Answer: 1884dde67ced589082c8b7043abce181
Problem 71
==========
Consider the fraction, n/d, where n and d are positive integers. If n<d
and HCF(n,d)=1, it is called a reduced proper fraction.
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3,
5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that 2/5 is the fraction immediately to the left of 3/7.
Answer: 71f38fa2f04db30be52f883d583bfd6f
Problem 72
==========
Consider the fraction, n/d, where n and d are positive integers. If n<d
and HCF(n,d)=1, it is called a reduced proper fraction.
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3,
5/7, 3/4, 4/5, 5/6, 6/7, 7/8
Answer: 0384fb529dc651fe0f460acff3e9ac5d
Problem 73
==========
Consider the fraction, n/d, where n and d are positive integers. If n<d
and HCF(n,d)=1, it is called a reduced proper fraction.
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3,
5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced
proper fractions for d ≤ 12,000?
Answer: 990a49eb474672444137fff1e5528a1b
Problem 74
==========
The number 145 is well known for the property that the sum of the
factorial of its digits is equal to 145:
1! + 4! + 5! = 1 + 24 + 120 = 145
Perhaps less well known is 169, in that it produces the longest chain of
numbers that link back to 169; it turns out that there are only three such
loops that exist:
How many chains, with a starting number below one million, contain exactly
sixty non-repeating terms?
Answer: 69cb3ea317a32c4e6143e665fdb20b14
Problem 75
==========
It turns out that 12 cm is the smallest length of wire that can be bent to
form an integer sided right angle triangle in exactly one way, but there
are many more examples.
12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)
Given that L is the length of the wire, for how many values of L ≤
1,500,000 can exactly one integer sided right angle triangle be formed?
Answer: 583e391a7bd87f785412f72f486433cb
Problem 76
==========
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least
two positive integers?
Answer: 18ed0f01e082beffe0049ae1272689d2
Problem 77
==========
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
What is the first value which can be written as the sum of primes in over
five thousand different ways?
Answer: e2c420d928d4bf8ce0ff2ec19b371514
Problem 78
==========
Let p(n) represent the number of different ways in which n coins can be
separated into piles. For example, five coins can separated into piles in
exactly seven different ways, so p(5)=7.
OOOOO
OOOO O
OOO OO
OOO O O
OO OO O
OO O O O
O O O O O
Find the least value of n for which p(n) is divisible by one million.
Answer: ef2a8695e428116131cc94c651d0e566
Problem 79
==========
A common security method used for online banking is to ask the user for
three random characters from a passcode. For example, if the passcode was
531278, they may ask for the 2nd, 3rd, and 5th characters; the expected
reply would be: 317.
Given that the three characters are always asked for in order, analyse the
file so as to determine the shortest possible secret passcode of unknown
length.
Visible links
1. keylog.txt
Answer: 3ccc6e16d99b21d42948f6d49b90fa30
Problem 80
==========
It is well known that if the square root of a natural number is not an
integer, then it is irrational. The decimal expansion of such square roots
is infinite without any repeating pattern at all.
For the first one hundred natural numbers, find the total of the digital
sums of the first one hundred decimal digits for all the irrational square
roots.
Answer: 6cc501a25298e4051886ef1a126e9484
Problem 81
==========
In the 5 by 5 matrix below, the minimal path sum from the top left to the
bottom right, by only moving to the right and down, is indicated in bold
red and is equal to 2427.
Find the minimal path sum, in [1]matrix.txt, a 31K text file containing a
80 by 80 matrix, from the top left to the bottom right by only moving
right and down.
Visible links
1. matrix.txt
Answer: f9ffec84499832add77e6a8bb00246ec
Problem 82
==========
The minimal path sum in the 5 by 5 matrix below, by starting in any cell
in the left column and finishing in any cell in the right column, and only
moving up, down, and right, is indicated in red and bold; the sum is equal
to 994.
Find the minimal path sum, in [2]matrix.txt, a 31K text file containing a
80 by 80 matrix, from the left column to the right column.
Visible links
1. problem=81
2. matrix.txt
Answer: e6b3b1cd89b018d4754cf63863f6690a
Problem 83
==========
In the 5 by 5 matrix below, the minimal path sum from the top left to the
bottom right, by moving left, right, up, and down, is indicated in bold
red and is equal to 2297.
Find the minimal path sum, in [2]matrix.txt, a 31K text file containing a
80 by 80 matrix, from the top left to the bottom right by moving left,
right, up, and down.
Visible links
1. problem=81
2. matrix.txt
Answer: 61b28c4fbe8560003ee50fa5619d7a1e
Problem 84
==========
In the game, Monopoly, the standard board is set up in the following way:
A player starts on the GO square and adds the scores on two 6-sided dice
to determine the number of squares they advance in a clockwise direction.
Without any further rules we would expect to visit each square with equal
probability: 2.5%. However, landing on G2J (Go To Jail), CC (community
chest), and CH (chance) changes this distribution.
In addition to G2J, and one card from each of CC and CH, that orders the
player to go directly to jail, if a player rolls three consecutive
doubles, they do not advance the result of their 3rd roll. Instead they
proceed directly to jail.
At the beginning of the game, the CC and CH cards are shuffled. When a
player lands on CC or CH they take a card from the top of the respective
pile and, after following the instructions, it is returned to the bottom
of the pile. There are sixteen cards in each pile, but for the purpose of
this problem we are only concerned with cards that order a movement; any
instruction not concerned with movement will be ignored and the player
will remain on the CC/CH square.
1. Advance to GO
2. Go to JAIL
1. Advance to GO
2. Go to JAIL
3. Go to C1
4. Go to E3
5. Go to H2
6. Go to R1
7. Go to next R (railway company)
8. Go to next R
9. Go to next U (utility company)
10. Go back 3 squares.
If, instead of using two 6-sided dice, two 4-sided dice are used, find the
six-digit modal string.
Answer: ead3264438ef83a8c2da2e98067b4445
Problem 85
==========
p_085.gif
Answer: 92bf5e6240737e0326ea59846a83e076
Problem 86
==========
However, there are up to three "shortest" path candidates for any given
cuboid and the shortest route doesn't always have integer length.
Find the least value of M such that the number of solutions first exceeds
one million.
p_086.gif
Answer: f5c3dd7514bf620a1b85450d2ae374b1
Problem 87
==========
The smallest number expressible as the sum of a prime square, prime cube,
and prime fourth power is 28. In fact, there are exactly four numbers
below fifty that can be expressed in such a way:
How many numbers below fifty million can be expressed as the sum of a
prime square, prime cube, and prime fourth power?
Answer: e7fb7907f1af626cc42e787e367ec602
Problem 88
==========
A natural number, N, that can be written as the sum and product of a given
set of at least two natural numbers, {a[1], a[2], ... , a[k]} is called a
product-sum number: N = a[1] + a[2] + ... + a[k] = a[1] × a[2] × ... ×
a[k].
For example, 6 = 1 + 2 + 3 = 1 × 2 × 3.
For a given set of size, k, we shall call the smallest N with this
property a minimal product-sum number. The minimal product-sum numbers for
sets of size, k = 2, 3, 4, 5, and 6 are as follows.
k=2: 4 = 2 × 2 = 2 + 2
k=3: 6 = 1 × 2 × 3 = 1 + 2 + 3
k=4: 8 = 1 × 1 × 2 × 4 = 1 + 1 + 2 + 4
k=5: 8 = 1 × 1 × 2 × 2 × 2 = 1 + 1 + 2 + 2 + 2
k=6: 12 = 1 × 1 × 1 × 1 × 2 × 6 = 1 + 1 + 1 + 1 + 2 + 6
Hence for 2≤k≤6, the sum of all the minimal product-sum numbers is
4+6+8+12 = 30; note that 8 is only counted once in the sum.
What is the sum of all the minimal product-sum numbers for 2≤k≤12000?
Answer: ffde7251f43906d31534ae69fa555757
Problem 89
==========
The rules for writing Roman numerals allow for many ways of writing each
number (see [1]About Roman Numerals...). However, there is always a "best"
way of writing a particular number.
For example, the following represent all of the legitimate ways of writing
the number sixteen:
IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI
The last example being considered the most efficient, as it uses the least
number of numerals.
The 11K text file, [2]roman.txt, contains one thousand numbers written in
valid, but not necessarily minimal, Roman numerals; that is, they are
arranged in descending units and obey the subtractive pair rule (see
[3]About Roman Numerals... for the definitive rules for this problem).
Find the number of characters saved by writing each of these in their
minimal form.
Note: You can assume that all the Roman numerals in the file contain no
more than four consecutive identical units.
Visible links
1. about=roman_numerals
2. roman.txt
3. about=roman_numerals
Answer: 5c572eca050594c7bc3c36e7e8ab9550
Problem 90
==========
But because we are allowing 6 and 9 to be reversed, the two distinct sets
in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9}
for the purpose of forming 2-digit numbers.
How many distinct arrangements of the two cubes allow for all of the
square numbers to be displayed?
p_090.gif
Answer: 6a61d423d02a1c56250dc23ae7ff12f3
Problem 91
==========
The points P (x[1], y[1]) and Q (x[2], y[2]) are plotted at integer
co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.
There are exactly fourteen triangles containing a right angle that can be
formed when each co-ordinate lies between 0 and 2 inclusive; that is,
0 ≤ x[1], y[1], x[2], y[2] ≤ 2.
Given that 0 ≤ x[1], y[1], x[2], y[2] ≤ 50, how many right triangles can
be formed?
p_091_1.gif
p_091_2.gif
Answer: e8dc153260a59d4f236cfd7439d5dfd3
Problem 92
==========
For example,
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
How many starting numbers below ten million will arrive at 89?
Answer: 6cee918c0612bccc2dac03d05e07035f
Problem 93
==========
By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and
making use of the four arithmetic operations (+, −, *, /) and
brackets/parentheses, it is possible to form different positive integer
targets.
For example,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)
Note that concatenations of the digits, like 12 + 34, are not allowed.
Find the set of four distinct digits, a < b < c < d, for which the longest
set of consecutive positive integers, 1 to n, can be obtained, giving your
answer as a string: abcd.
Answer: 26588e932c7ccfa1df309280702fe1b5
Problem 94
==========
Find the sum of the perimeters of all almost equilateral triangles with
integral side lengths and area and whose perimeters do not exceed one
billion (1,000,000,000).
Answer: 3218c6bb59f2539ec39ad4bf37c10913
Problem 95
==========
The proper divisors of a number are all the divisors excluding the number
itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As
the sum of these divisors is equal to 28, we call it a perfect number.
Interestingly the sum of the proper divisors of 220 is 284 and the sum of
the proper divisors of 284 is 220, forming a chain of two numbers. For
this reason, 220 and 284 are called an amicable pair.
Perhaps less well known are longer chains. For example, starting with
12496, we form a chain of five numbers:
Find the smallest member of the longest amicable chain with no element
exceeding one million.
Answer: cd2018beeece5fb0a71a96308e567bde
Problem 96
==========
Su Doku (Japanese meaning number place) is the name given to a popular
puzzle concept. Its origin is unclear, but credit must be attributed to
Leonhard Euler who invented a similar, and much more difficult, puzzle
idea called Latin Squares. The objective of Su Doku puzzles, however, is
to replace the blanks (or zeros) in a 9 by 9 grid in such that each row,
column, and 3 by 3 box contains each of the digits 1 to 9. Below is an
example of a typical starting puzzle grid and its solution grid.
┌───────┬───────┬───────┐ ┌───────┬───────┬───────┐
│ 0 0 3 │ 0 2 0 │ 6 0 0 │ │ 4 8 3 │ 9 2 1 │ 6 5 7 │
│ 9 0 0 │ 3 0 5 │ 0 0 1 │ │ 9 6 7 │ 3 4 5 │ 8 2 1 │
│ 0 0 1 │ 8 0 6 │ 4 0 0 │ │ 2 5 1 │ 8 7 6 │ 4 9 3 │
├───────┼───────┼───────┤ ├───────┼───────┼───────┤
│ 0 0 8 │ 1 0 2 │ 9 0 0 │ │ 5 4 8 │ 1 3 2 │ 9 7 6 │
│ 7 0 0 │ 0 0 0 │ 0 0 8 │ │ 7 2 9 │ 5 6 4 │ 1 3 8 │
│ 0 0 6 │ 7 0 8 │ 2 0 0 │ │ 1 3 6 │ 7 9 8 │ 2 4 5 │
├───────┼───────┼───────┤ ├───────┼───────┼───────┤
│ 0 0 2 │ 6 0 9 │ 5 0 0 │ │ 3 7 2 │ 6 8 9 │ 5 1 4 │
│ 8 0 0 │ 2 0 3 │ 0 0 9 │ │ 8 1 4 │ 2 5 3 │ 7 6 9 │
│ 0 0 5 │ 0 1 0 │ 3 0 0 │ │ 6 9 5 │ 4 1 7 │ 3 8 2 │
└───────┴───────┴───────┘ └───────┴───────┴───────┘
A well constructed Su Doku puzzle has a unique solution and can be solved
by logic, although it may be necessary to employ "guess and test" methods
in order to eliminate options (there is much contested opinion over this).
The complexity of the search determines the difficulty of the puzzle; the
example above is considered easy because it can be solved by straight
forward direct deduction.
By solving all fifty puzzles find the sum of the 3-digit numbers found in
the top left corner of each solution grid; for example, 483 is the 3-digit
number found in the top left corner of the solution grid above.
Visible links
1. sudoku.txt
Answer: 26f6abfa0d7725fef678e371897d5df0
Problem 97
==========
The first known prime found to exceed one million digits was discovered in
1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly
2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1,
have been found which contain more digits.
Problem 98
==========
What is the largest square number formed by any member of such a pair?
NOTE: All anagrams formed must be contained in the given text file.
Visible links
1. words.txt
Answer: 36b3b5f54143786b7ab2ebb6bcd06e75
Problem 99
==========
Comparing two numbers written in index form like 2^11 and 3^7 is not
difficult, as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.
Using [1]base_exp.txt, a 22K text file containing one thousand lines with
a base/exponent pair on each line, determine which line number has the
greatest numerical value.
NOTE: The first two lines in the file represent the numbers in the example
given above.
Visible links
1. base_exp.txt
Answer: 1ecfb463472ec9115b10c292ef8bc986
Problem 100
===========
The next such arrangement, for which there is exactly 50% chance of taking
two blue discs at random, is a box containing eighty-five blue discs and
thirty-five red discs.
Answer: 21156e3acc4ca35b7a318c541a0648d5
Problem 101
===========
Suppose we were only given the first two terms of this sequence. Working
on the principle that "simple is best" we should assume a linear
relationship and predict the next term to be 15 (common difference 7).
Even if we were presented with the first three terms, by the same
principle of simplicity, a quadratic relationship should be assumed.
OP(1, n) = 1 1, 1, 1, 1, ...
OP(2, n) = 7n−6 1, 8, 15, ...
OP(3, n) = 6n^2−11n+6 1, 8, 27, 58, ...
OP(4, n) = n^3 1, 8, 27, 64, 125, ...
u[n] = 1 − n + n^2 − n^3 + n^4 − n^5 + n^6 − n^7 + n^8 − n^9 + n^10
Problem 102
===========
It can be verified that triangle ABC contains the origin, whereas triangle
XYZ does not.
NOTE: The first two examples in the file represent the triangles in the
example given above.
Visible links
1. triangles.txt
Answer: 74db120f0a8e5646ef5a30154e9f6deb
Problem 103
===========
Let S(A) represent the sum of elements in set A of size n. We shall call
it a special sum set if for any two non-empty disjoint subsets, B and C,
the following properties are true:
n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}
It seems that for a given optimum set, A = {a[1], a[2], ... , a[n]}, the
next optimum set is of the form B = {b, a[1]+b, a[2]+b, ... ,a[n]+b},
where b is the "middle" element on the previous row.
Given that A is an optimum special sum set for n = 7, find its set string.
Visible links
1. problem=105
2. problem=106
Answer: af8c238336c2a79bb81a24b3fef3330d
Problem 104
===========
It turns out that F[541], which contains 113 digits, is the first
Fibonacci number for which the last nine digits are 1-9 pandigital
(contain all the digits 1 to 9, but not necessarily in order). And
F[2749], which contains 575 digits, is the first Fibonacci number for
which the first nine digits are 1-9 pandigital.
Given that F[k] is the first Fibonacci number for which the first nine
digits AND the last nine digits are 1-9 pandigital, find k.
Answer: c8771ddd4df191098d70a8e94dd1cde7
Problem 105
===========
Let S(A) represent the sum of elements in set A of size n. We shall call
it a special sum set if for any two non-empty disjoint subsets, B and C,
the following properties are true:
For example, {81, 88, 75, 42, 87, 84, 86, 65} is not a special sum set
because 65 + 87 + 88 = 75 + 81 + 84, whereas {157, 150, 164, 119, 79, 159,
161, 139, 158} satisfies both rules for all possible subset pair
combinations and S(A) = 1286.
Problem 106
===========
Let S(A) represent the sum of elements in set A of size n. We shall call
it a special sum set if for any two non-empty disjoint subsets, B and C,
the following properties are true:
For this problem we shall assume that a given set contains n strictly
increasing elements and it already satisfies the second rule.
For n = 12, how many of the 261625 subset pairs that can be obtained need
to be tested for equality?
Visible links
1. problem=103
2. problem=105
Answer: c8fd9e36fdeb06bcc93a0732c667b6d8
Problem 107
===========
┌──────┬────┬────┬────┬────┬────┬────┬────┐
│ │ A │ B │ C │ D │ E │ F │ G │
├──────┼────┼────┼────┼────┼────┼────┼────┤
│ A │ - │ 16 │ 12 │ 21 │ - │ - │ - │
├──────┼────┼────┼────┼────┼────┼────┼────┤
│ B │ 16 │ - │ - │ 17 │ 20 │ - │ - │
├──────┼────┼────┼────┼────┼────┼────┼────┤
│ C │ 12 │ - │ - │ 28 │ - │ 31 │ - │
├──────┼────┼────┼────┼────┼────┼────┼────┤
│ D │ 21 │ 17 │ 28 │ - │ 18 │ 19 │ 23 │
├──────┼────┼────┼────┼────┼────┼────┼────┤
│ E │ - │ 20 │ - │ 18 │ - │ - │ 11 │
├──────┼────┼────┼────┼────┼────┼────┼────┤
│ F │ - │ - │ 31 │ 19 │ - │ - │ 27 │
├──────┼────┼────┼────┼────┼────┼────┼────┤
│ G │ - │ - │ - │ 23 │ 11 │ 27 │ - │
└──────┴────┴────┴────┴────┴────┴────┴────┘
Visible links
1. network.txt
p_107_1.gif
p_107_2.gif
Answer: b0db1202ec966e7855ca23626eb285b8
Problem 108
===========
1 1 1
─ + ─ = ─
x y n
1 1 1
─ + ─ = ─
5 20 4
1 1 1
─ + ─ = ─
6 12 4
1 1 1
─ + ─ = ─
8 8 4
What is the least value of n for which the number of distinct solutions
exceeds one-thousand?
Visible links
1. problem=110
Answer: 765ba18edd2844db2db95fba25d2f3e7
Problem 109
===========
In the game of darts a player throws three darts at a target board which
is split into twenty equal sized sections numbered one to twenty.
The score of a dart is determined by the number of the region that the
dart lands in. A dart landing outside the red/green outer ring scores
zero. The black and cream regions inside this ring represent single
scores. However, the red/green outer ring and middle ring score double and
treble scores respectively.
At the centre of the board are two concentric circles called the bull
region, or bulls-eye. The outer bull is worth 25 points and the inner bull
is a double, worth 50 points.
There are many variations of rules but in the most popular game the
players will begin with a score 301 or 501 and the first player to reduce
their running total to zero is a winner. However, it is normal to play a
"doubles out" system, which means that the player must land a double
(including the double bulls-eye at the centre of the board) on their final
dart to win; any other dart that would reduce their running total to one
or lower means the score for that set of three darts is "bust".
┌──┬──┬──┐
│D3│ │ │
├──┼──┼──┤
│D1│D2│ │
├──┼──┼──┤
│S2│D2│ │
├──┼──┼──┤
│D2│D1│ │
├──┼──┼──┤
│S4│D1│ │
├──┼──┼──┤
│S1│S1│D2│
├──┼──┼──┤
│S1│T1│D1│
├──┼──┼──┤
│S1│S3│D1│
├──┼──┼──┤
│D1│D1│D1│
├──┼──┼──┤
│D1│S2│D1│
├──┼──┼──┤
│S2│S2│D1│
└──┴──┴──┘
How many distinct ways can a player checkout with a score less than 100?
p_109.gif
Answer: e6aebd5be1ba81557dbcc5f6f57bbe5c
Problem 110
===========
1 1 1
─ + ─ = ─
x y n
It can be verified that when n = 1260 there are 113 distinct solutions and
this is the least value of n for which the total number of distinct
solutions exceeds one hundred.
What is the least value of n for which the number of distinct solutions
exceeds four million?
NOTE: This problem is a much more difficult version of [1]Problem 108 and
as it is well beyond the limitations of a brute force approach it requires
a clever implementation.
Visible links
1. problem=108
Answer: 591a7a92f10322866e6a02f3b2386a1c
Problem 111
===========
We shall say that M(n, d) represents the maximum number of repeated digits
for an n-digit prime where d is the repeated digit, N(n, d) represents the
number of such primes, and S(n, d) represents the sum of these primes.
┌──────────┬─────────┬─────────┬─────────┐
│ Digit, d │ M(4, d) │ N(4, d) │ S(4, d) │
├──────────┼─────────┼─────────┼─────────┤
│ 0 │ 2 │ 13 │ 67061 │
├──────────┼─────────┼─────────┼─────────┤
│ 1 │ 3 │ 9 │ 22275 │
├──────────┼─────────┼─────────┼─────────┤
│ 2 │ 3 │ 1 │ 2221 │
├──────────┼─────────┼─────────┼─────────┤
│ 3 │ 3 │ 12 │ 46214 │
├──────────┼─────────┼─────────┼─────────┤
│ 4 │ 3 │ 2 │ 8888 │
├──────────┼─────────┼─────────┼─────────┤
│ 5 │ 3 │ 1 │ 5557 │
├──────────┼─────────┼─────────┼─────────┤
│ 6 │ 3 │ 1 │ 6661 │
├──────────┼─────────┼─────────┼─────────┤
│ 7 │ 3 │ 9 │ 57863 │
├──────────┼─────────┼─────────┼─────────┤
│ 8 │ 3 │ 1 │ 8887 │
├──────────┼─────────┼─────────┼─────────┤
│ 9 │ 3 │ 7 │ 48073 │
└──────────┴─────────┴─────────┴─────────┘
Answer: cdf4d134a3b0caa10a69e2771ac4fd36
Problem 112
===========
Clearly there cannot be any bouncy numbers below one-hundred, but just
over half of the numbers below one-thousand (525) are bouncy. In fact, the
least number for which the proportion of bouncy numbers first reaches 50%
is 538.
Surprisingly, bouncy numbers become more and more common and by the time
we reach 21780 the proportion of bouncy numbers is equal to 90%.
Find the least number for which the proportion of bouncy numbers is
exactly 99%.
Answer: e08c982713a1c2bd3637dd489199722e
Problem 113
===========
Answer: a9e504ee704c87f9bddad6d3ffe39532
Problem 114
===========
A row measuring seven units in length has red blocks with a minimum length
of three units placed on it, such that any two red blocks (which are
allowed to be different lengths) are separated by at least one black
square. There are exactly seventeen ways of doing this.
How many ways can a row measuring fifty units in length be filled?
NOTE: Although the example above does not lend itself to the possibility,
in general it is permitted to mix block sizes. For example, on a row
measuring eight units in length you could use red (3), black (1), and red
(4).
Answer: de48ca72bf252a8be7e0aad762eadcf8
Problem 115
===========
A row measuring n units in length has red blocks with a minimum length of
m units placed on it, such that any two red blocks (which are allowed to
be different lengths) are separated by at least one black square.
Let the fill-count function, F(m, n), represent the number of ways that a
row can be filled.
That is, for m = 3, it can be seen that n = 30 is the smallest value for
which the fill-count function first exceeds one million.
In the same way, for m = 10, it can be verified that F(10, 56) = 880711
and F(10, 57) = 1148904, so n = 57 is the least value for which the
fill-count function first exceeds one million.
For m = 50, find the least value of n for which the fill-count function
first exceeds one million.
Visible links
1. problem=114
Answer: 006f52e9102a8d3be2fe5614f42ba989
Problem 116
===========
A row of five black square tiles is to have a number of its tiles replaced
with coloured oblong tiles chosen from red (length two), green (length
three), or blue (length four).
If red tiles are chosen there are exactly seven ways this can be done.
┌╥───┐ ┌───╥┐
└╨───┘ └───╨┘
How many different ways can the black tiles in a row measuring fifty units
in length be replaced if colours cannot be mixed and at least one coloured
tile must be used?
Visible links
1. problem=117
Answer: c21ca0ec54e6d1646a953a480f68feb4
Problem 117
===========
Using a combination of black square tiles and oblong tiles chosen from:
red tiles measuring two units, green tiles measuring three units, and blue
tiles measuring four units, it is possible to tile a row measuring five
units in length in exactly fifteen different ways.
How many ways can a row measuring fifty units in length be tiled?
Visible links
1. problem=116
Answer: 542612809b3dd08cf518b85450fce8d6
Problem 118
===========
Using all of the digits 1 through 9 and concatenating them freely to form
decimal integers, different sets can be formed. Interestingly with the set
{2,5,47,89,631}, all of the elements belonging to it are prime.
How many distinct sets containing each of the digits one through nine
exactly once contain only prime elements?
Answer: 080cc5a4ec71a747e260e274bdb13b64
Problem 119
===========
The number 512 is interesting because it is equal to the sum of its digits
raised to some power: 5 + 1 + 2 = 8, and 8^3 = 512. Another example of a
number with this property is 614656 = 28^4.
We shall define a[n] to be the nth term of this sequence and insist that a
number must contain at least two digits to have a sum.
Find a[30].
Answer: 72fddfa6c52a120892ade628f3819da4
Problem 120
===========
For example, if a = 7 and n = 3, then r = 42: 6^3 + 8^3 = 728 ≡ 42 mod 49.
And as n varies, so too will r, but for a = 7 it turns out that r[max] =
42.
Answer: 0dd05ec40fe11279c2203b72e92a450a
Problem 121
===========
A bag contains one red disc and one blue disc. In a game of chance a
player takes a disc at random and its colour is noted. After each turn the
disc is returned to the bag, an extra red disc is added, and another disc
is taken at random.
The player pays £1 to play and wins if they have taken more blue discs
than red discs at the end of the game.
If the game is played for four turns, the probability of a player winning
is exactly 11/120, and so the maximum prize fund the banker should
allocate for winning in this game would be £10 before they would expect to
incur a loss. Note that any payout will be a whole number of pounds and
also includes the original £1 paid to play the game, so in the example
given the player actually wins £9.
Find the maximum prize fund that should be allocated to a single game in
which fifteen turns are played.
Answer: 51de85ddd068f0bc787691d356176df9
Problem 122
===========
n × n × ... × n = n^15
n × n = n^2
n^2 × n^2 = n^4
n^4 × n^4 = n^8
n^8 × n^4 = n^12
n^12 × n^2 = n^14
n^14 × n = n^15
n × n = n^2
n^2 × n = n^3
n^3 × n^3 = n^6
n^6 × n^6 = n^12
n^12 × n^3 = n^15
Answer: b710915795b9e9c02cf10d6d2bdb688c
Problem 123
===========
Let p[n] be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder
when (p[n]−1)^n + (p[n]+1)^n is divided by p[n]^2.
For example, when n = 3, p[3] = 5, and 4^3 + 6^3 = 280 ≡ 5 mod 25.
The least value of n for which the remainder first exceeds 10^9 is 7037.
Find the least value of n for which the remainder first exceeds 10^10.
Answer: 71497f728b86b55d965edbf1849cca8d
Problem 124
===========
Unsorted Sorted
n rad(n) n rad(n) k
1 1 1 1 1
2 2 2 2 2
3 3 4 2 3
4 2 8 2 4
5 5 3 3 5
6 6 9 3 6
7 7 5 5 7
8 2 6 6 8
9 3 7 7 9
10 10 10 10 10
Let E(k) be the kth element in the sorted n column; for example, E(4) = 8
and E(6) = 9.
Answer: f228d2e6f9099153388e9470180c8302
Problem 125
===========
Find the sum of all the numbers less than 10^8 that are both palindromic
and can be written as the sum of consecutive squares.
Answer: 1b5635e8ab723e01570ca783129493dd
Problem 126
===========
It turns out that 154 is the least value of n for which C(n) = 10.
p_126.gif
Answer: 387d6ae83cbc6fa0b9192b56bf095c49
Problem 127
===========
It turns out that abc-hits are quite rare and there are only thirty-one
abc-hits for c < 1000, with ∑c = 12523.
Answer: c6b1ae935b33c90a2c320b5f6ef3e4ba
Problem 128
===========
New rings are added in the same fashion, with the next rings being
numbered 8 to 19, 20 to 37, 38 to 61, and so on. The diagram below shows
the first three rings.
By finding the difference between tile n and each its six neighbours we
shall define PD(n) to be the number of those differences which are prime.
For example, working clockwise around tile 8 the differences are 12, 29,
11, 6, 1, and 13. So PD(8) = 3.
In the same way, the differences around tile 17 are 1, 17, 16, 1, 11, and
10, hence PD(17) = 2.
If all of the tiles for which PD(n) = 3 are listed in ascending order to
form a sequence, the 10th tile would be 271.
p_128.gif
Answer: 93a1925da4792b4fa5d2dbb6ebb7c4a2
Problem 129
===========
The least value of n for which A(n) first exceeds ten is 17.
Find the least value of n for which A(n) first exceeds one-million.
Answer: 82cd979a2b79600137aea54fa0bd944b
Problem 130
===========
You are given that for all primes, p > 5, that p − 1 is divisible by A(p).
For example, when p = 41, A(41) = 5, and 40 is divisible by 5.
However, there are rare composite values for which this is also true; the
first five examples being 91, 259, 451, 481, and 703.
Find the sum of the first twenty-five composite values of n for which
GCD(n, 10) = 1 and n − 1 is divisible by A(n).
Answer: 20594ea0ef7a2f4cf40d19a9b82a0beb
Problem 131
===========
There are some prime values, p, for which there exists a positive integer,
n, such that the expression n^3 + n^2p is a perfect cube.
What is perhaps most surprising is that for each prime with this property
the value of n is unique, and there are only four such primes below
one-hundred.
How many primes below one million have this remarkable property?
Answer: f7e6c85504ce6e82442c770f7c8606f0
Problem 132
===========
Answer: 5df3a36faa173a393a04a022b2d5d49d
Problem 133
===========
Find the sum of all the primes below one-hundred thousand that will never
be a factor of R(10^n).
Answer: c1d33d79d08cde65eaa78e4583ea0594
Problem 134
===========
In fact, with the exception of p[1] = 3 and p[2] = 5, for every pair of
consecutive primes, p[2] > p[1], there exist values of n for which the
last digits are formed by p[1] and n is divisible by p[2]. Let S be the
smallest of these values of n.
Answer: f12b07460d2586ea47b4d305ae0b0539
Problem 135
===========
It turns out that n = 1155 is the least value which has exactly ten
solutions.
How many values of n less than one million have exactly ten distinct
solutions?
Answer: c457d7ae48d08a6b84bc0b1b9bd7d474
Problem 136
===========
In fact there are twenty-five values of n below one hundred for which the
equation has a unique solution.
How many values of n less than fifty million have exactly one solution?
Answer: 91db9e8e6cb2dbf9c07a6e0429697336
Problem 137
===========
The corresponding values of x for the first five natural numbers are shown
below.
┌─────────┬───────┐
│x │A[F](x)│
├─────────┼───────┤
│√2−1 │1 │
├─────────┼───────┤
│1/2 │2 │
├─────────┼───────┤
│(√13−2)/3│3 │
├─────────┼───────┤
│(√89−5)/8│4 │
├─────────┼───────┤
│(√34−3)/5│5 │
└─────────┴───────┘
Answer: 44845aa0f47ec925a3b43e6460a55e27
Problem 138
===========
Consider the isosceles triangle with base length, b = 16, and legs, L =
17.
By using the Pythagorean theorem it can be seen that the height of the
triangle, h = √(17^2 − 8^2) = 15, which is one less than the base length.
With b = 272 and L = 305, we get h = 273, which is one more than the base
length, and this is the second smallest isosceles triangle with the
property that h = b ± 1.
p_138.gif
Answer: f7524f4d0d6d042c0f92a0d6469aff85
Problem 139
===========
Let (a, b, c) represent the three sides of a right angle triangle with
integral length sides. It is possible to place four such triangles
together to form a square with length c.
However, if (5, 12, 13) triangles were used then the hole would measure 7
by 7 and these could not be used to tile the 13 by 13 square.
Given that the perimeter of the right triangle is less than one-hundred
million, how many Pythagorean triangles would allow such a tiling to take
place?
p_139.gif
Answer: 1c343ba00e6d17d7239bf45869ffed0c
Problem 140
===========
For this problem we shall be concerned with values of x for which A[G](x)
is a positive integer.
The corresponding values of x for the first five natural numbers are shown
below.
┌───────────┬───────┐
│x │A[G](x)│
├───────────┼───────┤
│(√5−1)/4 │1 │
├───────────┼───────┤
│2/5 │2 │
├───────────┼───────┤
│(√22−2)/6 │3 │
├───────────┼───────┤
│(√137−5)/14│4 │
├───────────┼───────┤
│1/2 │5 │
└───────────┴───────┘
Answer: e5d75f96929ba250b2732aad52f3028c
Problem 141
===========
Find the sum of all progressive perfect squares below one trillion
(10^12).
Answer: 2aaefa1db80951be140183f9e8c0194e
Problem 142
===========
Find the smallest x + y + z with integers x > y > z > 0 such that x + y, x
− y, x + z, x − z, y + z, y − z are all perfect squares.
Answer: d3de282705508407532aa20ca8928e3b
Problem 143
===========
Let ABC be a triangle with all interior angles being less than 120
degrees. Let X be any point inside the triangle and let XA = p, XC = q,
and XB = r.
Torricelli was able to prove that if equilateral triangles AOB, BNC and
AMC are constructed on each side of triangle ABC, the circumscribed
circles of AOB, BNC, and AMC will intersect at a single point, T, inside
the triangle. Moreover he proved that T, called the Torricelli/Fermat
point, minimises p + q + r. Even more remarkable, it can be shown that
when the sum is minimised, AN = BM = CO = p + q + r and that AN, BM and CO
also intersect at T.
p_143_torricelli.gif
Answer: ec2d4c1a0c204d1f06ea5e2d189034f6
Problem 144
===========
The light beam in this problem starts at the point (0.0,10.1) just outside
the white cell, and the beam first impacts the mirror at (1.4,-9.6).
Each time the laser beam hits the surface of the ellipse, it follows the
usual law of reflection "angle of incidence equals angle of reflection."
That is, both the incident and reflected beams make the same angle with
the normal line at the point of incidence.
In the figure on the left, the red line shows the first two points of
contact between the laser beam and the wall of the white cell; the blue
line shows the line tangent to the ellipse at the point of incidence of
the first bounce.
The slope m of the tangent line at any point (x,y) of the given ellipse
is: m = −4x/y
The animation on the right shows the first 10 reflections of the beam.
How many times does the beam hit the internal surface of the white cell
before exiting?
p_144_1.gif
p_144_2.gif
Answer: 8dd48d6a2e2cad213179a3992c0be53c
Problem 145
===========
Some positive integers n have the property that the sum [ n + reverse(n) ]
consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and
409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409,
and 904 are reversible. Leading zeroes are not allowed in either n or
reverse(n).
Answer: 705e8444ad9c92e9a7589fb97515a9b6
Problem 146
===========
The smallest positive integer n for which the numbers n^2+1, n^2+3, n^2+7,
n^2+9, n^2+13, and n^2+27 are consecutive primes is 10. The sum of all
such integers n below one-million is 1242490.
Answer: 525bd2bf0e31b0f19b38a1d21f2f6a16
Problem 147
===========
There are 5 grids smaller than 3x2, vertical and horizontal dimensions
being important, i.e. 1x1, 2x1, 3x1, 1x2 and 2x2. If each of them is
cross-hatched, the following number of different rectangles could be
situated within those smaller grids:
1x1: 1
2x1: 4
3x1: 8
1x2: 4
2x2: 18
How many different rectangles could be situated within 47x43 and smaller
grids?
p_147.gif
Answer: d0fca7d85d4a4df043a2ae5772ea472e
Problem 148
===========
We can easily verify that none of the entries in the first seven rows of
Pascal's triangle are divisible by 7:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
However, if we check the first one hundred rows, we will find that only
2361 of the 5050 entries are not divisible by 7.
Find the number of entries which are not divisible by 7 in the first one
billion (10^9) rows of Pascal's triangle.
Answer: 8a631ab4e3d06baf88299bf4e501b837
Problem 149
===========
Looking at the table below, it is easy to verify that the maximum possible
sum of adjacent numbers in any direction (horizontal, vertical, diagonal
or anti-diagonal) is 16 (= 8 + 7 + 1).
┌────┬────┬────┬─────┐
│ −2 │ 5 │ 3 │ 2 │
├────┼────┼────┼─────┤
│ 9 │ −6 │ 5 │ 1 │
├────┼────┼────┼─────┤
│ 3 │ 2 │ 7 │ 3 │
├────┼────┼────┼─────┤
│ −1 │ 8 │ −4 │ 8 │
└────┴────┴────┴─────┘
The terms of s are then arranged in a 2000×2000 table, using the first
2000 numbers to fill the first row (sequentially), the next 2000 numbers
to fill the second row, and so on.
Finally, find the greatest sum of (any number of) adjacent entries in any
direction (horizontal, vertical, diagonal or anti-diagonal).
Answer: 96affc386f4b786c2521a32944424982
Problem 150
===========
In the example below, it can be easily verified that the marked triangle
satisfies this condition having a sum of −42.
t := 0
for k = 1 up to k = 500500:
t := (615949*t + 797807) modulo 2^20
s[k] := t−2^19
Our triangular array is then formed using the pseudo-random numbers thus:
s[1]
s[2] s[3]
s[4] s[5] s[6]
s[7] s[8] s[9] s[10]
...
Sub-triangles can start at any element of the array and extend down as far
as we like (taking-in the two elements directly below it from the next
row, the three elements directly below from the row after that, and so
on).
The "sum of a sub-triangle" is defined as the sum of all the elements it
contains.
Find the smallest possible sub-triangle sum.
p_150.gif
Answer: 1802939e514020769701c59b422c0498
Problem 151
===========
A printing shop runs 16 batches (jobs) every week and each batch requires
a sheet of special colour-proofing paper of size A5.
Every Monday morning, the foreman opens a new envelope, containing a large
sheet of the special paper with size A1.
He proceeds to cut it in half, thus getting two sheets of size A2. Then he
cuts one of them in half to get two sheets of size A3 and so on until he
obtains the A5-size sheet needed for the first batch of the week.
At the beginning of each subsequent batch, he takes from the envelope one
sheet of paper at random. If it is of size A5, he uses it. If it is
larger, he repeats the 'cut-in-half' procedure until he has what he needs
and any remaining sheets are always placed back in the envelope.
Excluding the first and last batch of the week, find the expected number
of times (during each week) that the foreman finds a single sheet of paper
in the envelope.
Give your answer rounded to six decimal places using the format x.xxxxxx .
p_151.gif
Answer: fb84a530fa9a8199edfadd618727fb70
Problem 152
===========
There are several ways to write the number 1/2 as a sum of inverse squares
using distinct integers.
In fact, only using integers between 2 and 45 inclusive, there are exactly
three ways to do it, the remaining two being:
{2,3,4,6,7,9,10,20,28,35,36,45} and {2,3,4,6,7,9,12,15,28,30,35,36,45}.
How many ways are there to write the number 1/2 as a sum of inverse
squares using distinct integers between 2 and 80 inclusive?
p_152_sum.gif
Answer: 34ed066df378efacc9b924ec161e7639
Problem 153
===========
As we all know the equation x^2=-1 has no solutions for real x.
If we however introduce the imaginary number i this equation has two
solutions: x=i and x=-i.
If we go a step further the equation (x-3)^2=-4 has two complex solutions:
x=3+2i and x=3-2i.
x=3+2i and x=3-2i are called each others' complex conjugate.
Numbers of the form a+bi are called complex numbers.
In general a+bi and a−bi are each other's complex conjugate.
A Gaussian Integer is a complex number a+bi such that both a and b are
integers.
The regular integers are also Gaussian integers (with b=0).
To distinguish them from Gaussian integers with b ≠ 0 we call such
integers "rational integers."
A Gaussian integer is called a divisor of a rational integer n if the
result is also a Gaussian integer.
If for example we divide 5 by 1+2i we can simplify in the following
manner:
Multiply numerator and denominator by the complex conjugate of 1+2i: 1−2i.
The result is .
So 1+2i is a divisor of 5.
Note that 1+i is not a divisor of 5 because .
Note also that if the Gaussian Integer (a+bi) is a divisor of a rational
integer n, then its complex conjugate (a−bi) is also a divisor of n.
In fact, 5 has six divisors such that the real part is positive: {1, 1 +
2i, 1 − 2i, 2 + i, 2 − i, 5}.
The following is a table of all of the divisors for the first five
positive rational integers:
┌───┬──────────────────────────────┬───────────────┐
│ n │ Gaussian integer divisors │ Sum s(n) of │
│ │ with positive real part │ thesedivisors │
├───┼──────────────────────────────┼───────────────┤
│ 1 │ 1 │ 1 │
├───┼──────────────────────────────┼───────────────┤
│ 2 │ 1, 1+i, 1-i, 2 │ 5 │
├───┼──────────────────────────────┼───────────────┤
│ 3 │ 1, 3 │ 4 │
├───┼──────────────────────────────┼───────────────┤
│ 4 │ 1, 1+i, 1-i, 2, 2+2i, 2-2i,4 │ 13 │
├───┼──────────────────────────────┼───────────────┤
│ 5 │ 1, 1+2i, 1-2i, 2+i, 2-i, 5 │ 12 │
└───┴──────────────────────────────┴───────────────┘
p_153_formule1.gif
p_153_formule2.gif
p_153_formule5.gif
p_153_formule6.gif
Answer: 08ec9d6e6c2275d37e7a227fb2d1f06f
Problem 154
===========
Then, we calculate the number of paths leading from the apex to each
position:
A path starts at the apex and progresses downwards to any of the three
spheres directly below the current position.
The result is Pascal's pyramid and the numbers at each level n are the
coefficients of the trinomial expansion (x + y + z)^n.
p_154_pyramid.gif
Answer: de866633fa075beb3897cbbc8abf2400
Problem 155
===========
Find D(18).
p_155_capsmu.gif
p_155_capacitors1.gif
p_155_capsform.gif
Answer: da0a3fc900cc8ae42d514e280524ee39
Problem 156
===========
Starting from zero the natural numbers are written down in base 10 like
this:
0 1 2 3 4 5 6 7 8 9 10 11 12....
Consider the digit d=1. After we write down each number n, we will update
the number of ones that have occurred and call this number f(n,1). The
first values for f(n,1), then, are as follows:
n f(n,1)
0 0
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 2
11 4
12 5
In the same manner the function f(n,d) gives the total number of digits d
that have been written down after the number n has been written.
In fact, for every digit d ≠ 0, 0 is the first solution of the equation
f(n,d)=n.
Let s(d) be the sum of all the solutions for which f(n,d)=n.
You are given that s(1)=22786974071.
Note: if, for some n, f(n,d)=n for more than one value of d this value of
n is counted again for every value of d for which f(n,d)=n.
Answer: ac0c6b67ed28cebb02b802e7a204aaee
Problem 157
===========
Answer: c96fc71df4ef8f6420fda7958957538c
Problem 158
===========
Answer: 6070fa194890e52b2989af5b542aee90
Problem 159
===========
A composite number can be factored many different ways. For instance, not
including multiplication by one, 24 can be factored in 7 distinct ways:
24 = 2x2x2x3
24 = 2x3x4
24 = 2x2x6
24 = 4x6
24 = 3x8
24 = 2x12
24 = 24
Recall that the digital root of a number, in base 10, is found by adding
together the digits of that number, and repeating that process until a
number is arrived at that is less than 10. Thus the digital root of 467 is
8.
We shall call a Digital Root Sum (DRS) the sum of the digital roots of the
individual factors of our number.
The chart below demonstrates all of the DRS values for 24.
┌─────────────┬────────────────┐
│Factorisation│Digital Root Sum│
├─────────────┼────────────────┤
│2x2x2x3 │ 9 │
├─────────────┼────────────────┤
│2x3x4 │ 9 │
├─────────────┼────────────────┤
│2x2x6 │ 10 │
├─────────────┼────────────────┤
│4x6 │ 10 │
├─────────────┼────────────────┤
│3x8 │ 11 │
├─────────────┼────────────────┤
│2x12 │ 5 │
├─────────────┼────────────────┤
│24 │ 6 │
└─────────────┴────────────────┘
Answer: 2ab79df40adc1028d1fa83a6333db907
Problem 160
===========
For any N, let f(N) be the last five digits before the trailing zeroes in
N!.
For example,
9! = 362880 so f(9)=36288
10! = 3628800 so f(10)=36288
20! = 2432902008176640000 so f(20)=17664
Find f(1,000,000,000,000)
Answer: e51ada1e23f810eb1b51a18bb6825f85
Problem 161
===========
If all possible orientations are taken into account there are six:
p_161_trio1.gif
p_161_trio3.gif
p_161_k9.gif
Answer: 975ccc38bb5402c5b485f3de5928d919
Problem 162
===========
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
The hexadecimal number AF when written in the decimal number system equals
10x16+15=175.
In the 3-digit hexadecimal numbers 10A, 1A0, A10, and A01 the digits 0,1
and A are all present.
Like numbers written in base ten we write hexadecimal numbers without
leading zeroes.
(A,B,C,D,E and F in upper case, without any leading or trailing code that
marks the number as hexadecimal and without leading zeroes , e.g. 1A3F and
not: 1a3f and not 0x1a3f and not $1A3F and not #1A3F and not 0000001A3F)
Answer: 049419b9fdad9af74d5888626fff56a3
Problem 163
===========
T(1) = 16
T(2) = 104
Find T(36).
p_163.gif
Answer: a4f66a42a5b5dc395d00463d77e0a0c6
Problem 164
===========
How many 20 digit numbers n (without any leading zero) exist such that no
three consecutive digits of n have a sum greater than 9?
Answer: 6e96debf3bfe7cc132401bafe5a5d6d6
Problem 165
===========
Moreover when two segments have exactly one point in common it might be
the case that that common point is an endpoint of either one of the
segments or of both. If a common point of two segments is not an endpoint
of either of the segments it is an interior point of both segments.
We will call a common point T of two segments L[1] and L[2] a true
intersection point of L[1] and L[2] if T is the only common point of L[1]
and L[2] and T is an interior point of both segments.
It can be verified that line segments L[2] and L[3] have a true
intersection point. We note that as the one of the end points of L[3]:
(22,40) lies on L[1] this is not considered to be a true point of
intersection. L[1] and L[2] have no common point. So among the three line
segments, we find one true intersection point.
Now let us do the same for 5000 line segments. To this end, we generate
20000 numbers using the so-called "Blum Blum Shub" pseudo-random number
generator.
s[0] = 290797
To create each line segment, we use four consecutive numbers t[n]. That
is, the first line segment is given by:
The first four numbers computed according to the above generator should
be: 27, 144, 12 and 232. The first segment would thus be (27,144) to
(12,232).
How many distinct true intersection points are found among the 5000 line
segments?
Answer: b87b096af5a545b4f7a45cfed4e67c87
Problem 166
===========
6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5
the sum of each row and each column has the value 12. Moreover the sum of
each diagonal is also 12.
In how many ways can you fill a 4x4 grid with the digits d, 0 ≤ d ≤ 9 so
that each row, each column, and both diagonals have the same sum?
Answer: e4f39f61ee7f1bfe433a177c07f5512f
Problem 167
===========
For two positive integers a and b, the Ulam sequence U(a,b) is defined by
U(a,b)[1] = a, U(a,b)[2] = b and for k > 2,U(a,b)[k] is the smallest
integer greater than U(a,b)[(k-1)] which can be written in exactly one way
as the sum of two distinct previous members of U(a,b).
Answer: aa5b61f6f4d96cbaeb5944b8fcdf64a3
Problem 168
===========
Consider the number 142857. We can right-rotate this number by moving the
last digit (7) to the front of it, giving us 714285.
It can be verified that 714285=5×142857.
This demonstrates an unusual property of 142857: it is a divisor of its
right-rotation.
Find the last 5 digits of the sum of all integers n, 10 < n < 10^100, that
have this property.
Answer: 39e7aab76650b018578830bc6dba007a
Problem 169
===========
For example, f(10)=5 since there are five different ways to express 10:
1 + 1 + 8
1 + 1 + 4 + 4
1 + 1 + 2 + 2 + 4
2 + 4 + 4
2 + 8
What is f(10^25)?
Answer: d149d4836703a8908becea56ddd3ed42
Problem 170
===========
6 × 1273 = 7638
6 × 9854 = 59124
Answer: 6ffe65352f717c1731666a107ace96c1
Problem 171
===========
For a positive integer n, let f(n) be the sum of the squares of the digits
(in base 10) of n, e.g.
f(3) = 3^2 = 9,
f(25) = 2^2 + 5^2 = 4 + 25 = 29,
f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36
Find the last nine digits of the sum of all n, 0 < n < 10^20, such that
f(n) is a perfect square.
Answer: ff586db8c4a5699ec78c645fcb27db7b
Problem 172
===========
How many 18-digit numbers n (without leading zeros) are there such that no
digit occurs more than three times in n?
Answer: f5f260ee21ead7478403c2ccd18a1829
Problem 173
===========
With one-hundred tiles, and not necessarily using all of the tiles at one
time, it is possible to form forty-one different square laminae.
Using up to one million tiles how many different square laminae can be
formed?
p_173_square_laminas.gif
Answer: 177f825c89a68aefae37b8dec9bb8a9b
Problem 174
===========
Given eight tiles it is possible to form a lamina in only one way: 3x3
square with a 1x1 hole in the middle. However, using thirty-two tiles it
is possible to form two distinct laminae.
Let N(n) be the number of t ≤ 1000000 such that t is type L(n); for
example, N(15) = 832.
p_173_square_laminas.gif
Answer: 73166006522ed7f51ed3e2ca66353b66
Problem 175
===========
For example, f(10)=5 since there are five different ways to express 10:
10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1
It can be shown that for every fraction p/q (p>0, q>0) there exists at
least one integer n such that
f(n)/f(n-1)=p/q.
Answer: 796dddd004c3465229058072f5b4583e
Problem 176
===========
Answer: c47c782ebaf8cdbb60eebfa86cd0003c
Problem 177
===========
We call such a quadrilateral for which all eight corner angles have
integer values when measured in degrees an "integer angled quadrilateral".
An example of an integer angled quadrilateral is a square, where all eight
corner angles are 45°. Another example is given by DAC = 20°, BAC = 60°,
ABD = 50°, CBD = 30°, BCA = 40°, DCA = 30°, CDB = 80°, ADB = 50°.
p_177_quad.gif
Answer: d7a85236af930db0f7e84f2de8ee7ac2
Problem 178
===========
Answer: 2ffddfa898fa5df6321aebea84d4f33f
Problem 179
===========
Find the number of integers 1 < n < 10^7, for which n and n + 1 have the
same number of positive divisors. For example, 14 has the positive
divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.
Answer: bafa0132bc7fc422a8d53bebb9d003c9
Problem 180
===========
Let s(x,y,z) = x + y + z.
Let t = u / v be the sum of all distinct s(x,y,z) for all golden triples
(x,y,z) of order 35.
All the s(x,y,z) and t must be in reduced form.
Find u + v.
Answer: 6459f69d151314c59df404868f45fa96
Problem 181
===========
Having three black objects B and one white object W they can be grouped in
7 ways like this:
In how many ways can sixty black objects B and forty white objects W be
thus grouped?
Answer: 0e1233ecbc058dabf54a8602eac55d95
Problem 182
===========
An issue when choosing e is that there should not be too many unconcealed
messages.
For instance, let p=19 and q=37.
Then n=19*37=703 and φ=18*36=648.
If we choose e=181, then, although gcd(181,648)=1 it turns out that all
possible messages
m (0≤m≤n-1) are unconcealed when calculating m^e mod n.
For any valid choice of e there exist some unconcealed messages.
It's important that the number of unconcealed messages is at a minimum.
Answer: 088ad9a61e60b9309e91cfc3ed27d729
Problem 183
===========
For example, if 11 is split into five equal parts, 11 = 2.2 + 2.2 + 2.2 +
2.2 + 2.2, then P = 2.2^5 = 51.53632.
It turns out that the maximum for N = 11 is found by splitting eleven into
four equal parts which leads to P[max] = (11/4)^4; that is, M(11) =
14641/256 = 57.19140625, which is a terminating decimal.
Answer: 438bc10af8f8eb366ec1371478ca3d3c
Problem 184
===========
Consider the set I[r] of points (x,y) with integer co-ordinates in the
interior of the circle with radius r, centered at the origin, i.e. x^2 +
y^2 < r^2.
For a radius of 2, I[2] contains the nine points (0,0), (1,0), (1,1),
(0,1), (-1,1), (-1,0), (-1,-1), (0,-1) and (1,-1). There are eight
triangles having all three vertices in I[2] which contain the origin in
the interior. Two of them are shown below, the others are obtained from
these by rotation.
For a radius of 3, there are 360 triangles containing the origin in the
interior and having all vertices in I[3] and for I[5] the number is 10600.
How many triangles are there containing the origin in the interior and
having all three vertices in I[105]?
p_184.gif
Answer: aa80f8619ed594e5d7852564457dbca6
Problem 185
===========
The game Number Mind is a variant of the well known game Master Mind.
For instance, given the following guesses for a 5-digit secret sequence,
90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct
5616185650518293 ;2 correct
3847439647293047 ;1 correct
5855462940810587 ;3 correct
9742855507068353 ;3 correct
4296849643607543 ;3 correct
3174248439465858 ;1 correct
4513559094146117 ;2 correct
7890971548908067 ;3 correct
8157356344118483 ;1 correct
2615250744386899 ;2 correct
8690095851526254 ;3 correct
6375711915077050 ;1 correct
6913859173121360 ;1 correct
6442889055042768 ;2 correct
2321386104303845 ;0 correct
2326509471271448 ;2 correct
5251583379644322 ;2 correct
1748270476758276 ;3 correct
4895722652190306 ;1 correct
3041631117224635 ;3 correct
1841236454324589 ;3 correct
2659862637316867 ;2 correct
Answer: 70f84864f21c4bf07ee53436580cd4bb
Problem 186
===========
Here are the records from a busy telephone system with one million users:
┌─────────────────┬─────────┬─────────┐
│RecNr │ Caller │ Called │
├─────────────────┼─────────┼─────────┤
│ 1 │ 200007 │ 100053 │
├─────────────────┼─────────┼─────────┤
│ 2 │ 600183 │ 500439 │
├─────────────────┼─────────┼─────────┤
│ 3 │ 600863 │ 701497 │
├─────────────────┼─────────┼─────────┤
│ ... │ ... │ ... │
└─────────────────┴─────────┴─────────┘
The telephone number of the caller and the called number in record n are
Caller(n) = S[2n-1] and Called(n) = S[2n] where S[1,2,3,...] come from the
"Lagged Fibonacci Generator":
From the start of the records, we say that any pair of users X and Y are
friends if X calls Y or vice-versa. Similarly, X is a friend of a friend
of Z if X is a friend of Y and Y is a friend of Z; and so on for longer
chains.
The Prime Minister's phone number is 524287. After how many successful
calls, not counting misdials, will 99% of the users (including the PM) be
a friend, or a friend of a friend etc., of the Prime Minister?
Answer: b21d68f1871abf1d5bbcf1206b3f1643
Problem 187
===========
There are ten composites below thirty containing precisely two, not
necessarily distinct, prime factors:4, 6, 9, 10, 14, 15, 21, 22, 25, 26.
How many composite integers, n < 10^8, have precisely two, not necessarily
distinct, prime factors?
Answer: b3e6977523511d2cbbef8fccb1e394db
Problem 188
===========
a↑↑1 = a,
a↑↑(k+1) = a^(a↑↑k).
Thus we have e.g. 3↑↑2 = 3^3 = 27, hence 3↑↑3 = 3^27 = 7625597484987 and
3↑↑4 is roughly 10^3.6383346400240996*10^12.
Answer: 62746b4d40a2b87c3dd6caee5d33e6a1
Problem 189
===========
We wish to colour the interior of each triangle with one of three colours:
red, green or blue, so that no two neighbouring triangles have the same
colour. Such a colouring shall be called valid. Here, two triangles are
said to be neighbouring if they share an edge.
Note: if they only share a vertex, then they are not neighbours.
How many distinct valid colourings are there for the above configuration?
p_189_grid.gif
p_189_colours.gif
Answer: d3dfdd37601678212b746c34699f1484
Problem 190
===========
Let S[m] = (x[1], x[2], ... , x[m]) be the m-tuple of positive real
numbers with x[1] + x[2] + ... + x[m] = m for which P[m] = x[1] * x[2]^2 *
... * x[m]^m is maximised.
Answer: 40cfcabd9b30d79ec81151fc756e9946
Problem 191
===========
Although there are eighty-one trinary strings for a 4-day period that can
be formed, exactly forty-three strings would lead to a prize:
OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO
Answer: e04dfa598b22a87570f63063f3ff595d
Problem 192
===========
Find the sum of all denominators of the best approximations to √n for the
denominator bound 10^12, where n is not a perfect square and 1 < n ≤
100000.
Answer: e5ec7d4b094709b1fcebbd73b10e6264
Problem 193
===========
Answer: ea29fcf755b560777b0b6d8714234d18
Problem 194
===========
Consider graphs built with the units A: and B: , where the units are glued
alongthe vertical edges as in the graph .
p_194_GraphA.png
p_194_GraphB.png
p_194_Fig.png
Answer: e070561d568a80a0e45d7835e3817ba4
Problem 195
===========
Let's call an integer sided triangle with exactly one angle of 60 degrees
a 60-degree triangle.
Let r be the radius of the inscribed circle of such a 60-degree triangle.
Find T(1053779).
Answer: 0fe232937a6d9f2a40825b86f568a38c
Problem 196
===========
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 65 66
. . .
A set of three primes is called a prime triplet if one of the three primes
has the other two as neighbours in the triangle.
For example, in the second row, the prime numbers 2 and 3 are elements of
some prime triplet.
Define S(n) as the sum of the primes in row n which are elements of any
prime triplet.
Then S(8)=60 and S(9)=37.
Answer: fb6b6b0a4b7b31ba429152bc0b6bd037
Problem 197
===========
Answer: c98cbf87636906f2465d481be815e454
Problem 198
===========
How many ambiguous numbers x = p/q,0 < x < 1/100, are there whose
denominator q does not exceed 10^8?
Answer: e59816f440fec9368c681314a127f3ee
Problem 199
===========
Three circles of equal radius are placed inside a larger circle such that
each pair of circles is tangent to one another and the inner circles do
not overlap. There are four uncovered "gaps" which are to be filled
iteratively with more tangent circles.
p_199_circles_in_circles.gif
Answer: 0f8fd87159c28ae5fea6ac91a95d48dd
Problem 200
===========
The first five squbes are 72, 108, 200, 392, and 500.
Interestingly, 200 is also the first number for which you cannot change
any single digit to make a prime; we shall call such numbers, prime-proof.
The next prime-proof sqube which contains the contiguous sub-string "200"
is 1992008.
Answer: c911c8e346aa813da5f5ed4f8e9128d8
Problem 201
===========
For any set A of numbers, let sum(A) be the sum of the elements of A.
Consider the set B = {1,3,6,8,10,11}.
There are 20 subsets of B containing three elements, and their sums are:
sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.
Some of these sums occur more than once, others are unique.
For a set A, let U(A,k) be the set of unique sums of k-element subsets of
A, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} and
sum(U(B,3)) = 156.
Determine the sum of all integers which are the sum of exactly one of the
50-element subsets of S, i.e. find sum(U(S,50)).
Answer: b7ad07c58c81a940b8ff067a13b2760d
Problem 202
===========
Label the vertices A, B and C. There are 2 ways in which a laser beam may
enter vertex C, bounce off 11 surfaces, then exit through the same vertex:
one way is shown below; the other is the reverse of that.
There are 80840 ways in which a laser beam may enter vertex C, bounce off
1000001 surfaces, then exit through the same vertex.
In how many ways can a laser beam enter at vertex C, bounce off
12017639147 surfaces, then exit through the same vertex?
p_201_laserbeam.gif
Answer: e9774949b5efad0d40d60ede379c5321
Problem 203
===========
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
.........
It can be seen that the first eight rows of Pascal's triangle contain
twelve distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35.
Find the sum of the distinct squarefree numbers in the first 51 rows of
Pascal's triangle.
Answer: d7ec16d216c923d3c927f46cfc914e92
Problem 204
===========
How many generalised Hamming numbers of type 100 are there which don't
exceed 10^9?
Answer: 4118ffb9edc56a033b5b27ca0bf34366
Problem 205
===========
Peter has nine four-sided (pyramidal) dice, each with faces numbered 1, 2,
3, 4.
Colin has six six-sided (cubic) dice, each with faces numbered 1, 2, 3, 4,
5, 6.
Peter and Colin roll their dice and compare totals: the highest total
wins. The result is a draw if the totals are equal.
What is the probability that Pyramidal Pete beats Cubic Colin? Give your
answer rounded to seven decimal places in the form 0.abcdefg
Answer: ba6c6c3888227a0799eca38191b587be
Problem 206
===========
Find the unique positive integer whose square has the form
1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.
Answer: 09f9d87cb4b1ebb34e1f607e55a351d8
Problem 207
===========
The first two such partitions are 4^1 = 2^1 + 2 and 4^1.5849625... =
2^1.5849625... + 6.
P(5) = 1/1
P(10) = 1/2
P(15) = 2/3
P(20) = 1/2
P(25) = 1/2
P(30) = 2/5
...
P(180) = 1/4
P(185) = 3/13
Answer: 3f17b264ed1717fe5fbde1e399bd501f
Problem 208
===========
Given that the robot starts facing North, how many journeys of 70 arcs in
length can it take that return it, after the final arc, to its starting
position?
(Any arc may be traversed multiple times.)
p_208_robotwalk.gif
Answer: 3010e33173f30e0aac79e84835b48823
Problem 209
===========
┌────┬────┬─────────┐
│ x │ y │x AND y │
├────┼────┼─────────┤
│ 0 │ 0 │ 0 │
├────┼────┼─────────┤
│ 0 │ 1 │ 0 │
├────┼────┼─────────┤
│ 1 │ 0 │ 0 │
├────┼────┼─────────┤
│ 1 │ 1 │ 1 │
└────┴────┴─────────┘
┌────┬────┬─────────┐
│ x │ y │x XOR y │
├────┼────┼─────────┤
│ 0 │ 0 │ 0 │
├────┼────┼─────────┤
│ 0 │ 1 │ 1 │
├────┼────┼─────────┤
│ 1 │ 0 │ 1 │
├────┼────┼─────────┤
│ 1 │ 1 │ 0 │
└────┴────┴─────────┘
Answer: 954157aa4762df2ee29580ee5a351b13
Problem 210
===========
Consider the set S(r) of points (x,y) with integer coordinates satisfying
|x| + |y| ≤ r.
Let O be the point (0,0) and C the point (r/4,r/4).
Let N(r) be the number of points B in S(r), so that the triangle OBC has
an obtuse angle, i.e. the largest angle α satisfies 90°<α<180°.
So, for example, N(4)=24 and N(8)=100.
What is N(1,000,000,000)?
Answer: 0c808b02789c4db462322ab2ac070bbb
Problem 211
===========
For a positive integer n, let σ[2](n) be the sum of the squares of its
divisors. For example,
Find the sum of all n, 0 < n < 64,000,000 such that σ[2](n) is a perfect
square.
Answer: 5fe0ed146690e7bca448687a94353a73
Problem 212
===========
An axis-aligned cuboid, specified by parameters { (x[0],y[0],z[0]),
(dx,dy,dz) }, consists of all points (X,Y,Z) such that x[0] ≤ X ≤ x[0]+dx,
y[0] ≤ Y ≤ y[0]+dy and z[0] ≤ Z ≤ z[0]+dz. The volume of the cuboid is the
product, dx × dy × dz. The combined volume of a collection of cuboids is
the volume of their union and will be less than the sum of the individual
volumes if any cuboids overlap.
Answer: 76650c9c077929e1ce5a80a1ac81fa96
Problem 213
===========
A 30×30 grid of squares contains 900 fleas, initially one flea per square.
When a bell is rung, each flea jumps to an adjacent square at random
(usually 4 possibilities, except for fleas on the edge of the grid or at
the corners).
Answer: f81ee7dd444a3d895a4a446f9d115bf8
Problem 214
===========
Let φ be Euler's totient function, i.e. for a natural number n,φ(n) is the
number of k, 1 ≤ k ≤ n, for which gcd(k,n) = 1.
By iterating φ, each positive integer generates a decreasing chain of
numbers ending in 1.
E.g. if we start with 5 the sequence 5,4,2,1 is generated.
Here is a listing of all chains with length 4:
5,4,2,1
7,6,2,1
8,4,2,1
9,6,2,1
10,4,2,1
12,4,2,1
14,6,2,1
18,6,2,1
Only two of these chains start with a prime, their sum is 12.
What is the sum of all primes less than 40000000 which generate a chain of
length 25?
Answer: 1cefd865483c03552d5247ffb05685c7
Problem 215
===========
Consider the problem of building a wall out of 2×1 and 3×1 bricks
(horizontal×vertical dimensions) such that, for extra strength, the gaps
between horizontally-adjacent bricks never line up in consecutive layers,
i.e. never form a "running crack".
For example, the following 9×3 wall is not acceptable due to the running
crack shown in red:
There are eight ways of forming a crack-free 9×3 wall, written W(9,3) = 8.
Calculate W(32,10).
p_215_crackfree.gif
Answer: 60212c9ec4a6cd1d14277c32b6adf2d8
Problem 216
===========
Answer: e512153424a482deb9de401ac0465a72
Problem 217
===========
Let T(n) be the sum of all balanced numbers less than 10^n.
Thus: T(1) = 45, T(2) = 540 and T(5) = 334795890.
Answer: 11bff97aac06892e1a07ebf7febfa8db
Problem 218
===========
Consider the right angled triangle with sides a=7, b=24 and c=25.The area
of this triangle is 84, which is divisible by the perfect numbers 6 and
28.
Moreover it is a primitive right angled triangle as gcd(a,b)=1 and
gcd(b,c)=1.
Also c is a perfect square.
How many perfect right-angled triangles with c≤10^16 exist that are not
super-perfect?
Answer: cfcd208495d565ef66e7dff9f98764da
Problem 219
===========
Now suppose that it costs one penny to transmit a '0' bit, but four pence
to transmit a '1'.
Then the total cost of the prefix-free code shown above is 35 pence, which
happens to be the cheapest possible for the skewed pricing scheme in
question.
In short, we write Cost(6) = 35.
What is Cost(10^9) ?
Answer: 578c22ef288b88c60fbcf4541351aff5
Problem 220
===========
Let D[0] be the two-letter string "Fa". For n≥1, derive D[n] from D[n-1]
by the string-rewriting rules:
"a" → "aRbFR"
"b" → "LFaLb"
p_220.gif
Answer: e2018d8efde8ea00319f1adc042f150b
Problem 221
===========
A = p · q · r and 1 = 1 + 1 + 1
A p q r
Answer: cb000c24f653d9c8f78b74123e6515ab
Problem 222
===========
What is the length of the shortest pipe, of internal radius 50mm, that can
fully contain 21 balls of radii 30mm, 31mm, ..., 50mm?
Answer: 6984ba429b968467619ec98a8ee51abf
Problem 223
===========
How many barely acute triangles are there with perimeter ≤ 25,000,000?
Answer: cb875e59736a1967c8da8fc8062a6bc5
Problem 224
===========
How many barely obtuse triangles are there with perimeter ≤ 75,000,000?
Answer: c43cfb12750dee27b4b0d016261e831b
Problem 225
===========
The sequence 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201 ...
is defined by T[1] = T[2] = T[3] = 1 and T[n] = T[n-1] + T[n-2] + T[n-3].
It can be shown that 27 does not divide any terms of this sequence.
In fact, 27 is the first odd number with this property.
Find the 124^th odd number that does not divide any terms of the above
sequence.
Answer: f1981e4bd8a0d6d8462016d2fc6276b3
Problem 226
===========
The blancmange curve is the set of points (x,y) such that 0 ≤ x ≤ 1 and ,
where s(x) = the distance from x to the nearest integer.
The area under the blancmange curve is equal to ½, shown in pink in the
diagram below.
[1]blancmange curve
Let C be the circle with centre (¼,½) and radius ¼, shown in black in the
diagram.
Visible links
p_226_formula.gif
p_226_scoop2.gif
Answer: ce6fd32d1d2fb58c4c0c1f7962c39f04
Problem 227
===========
"The Chase" is a game played with two dice and an even number of players.
The players sit around a table; the game begins with two opposite players
having one die each. On each turn, the two players with a die roll it.
If a player rolls a 1, he passes the die to his neighbour on the left; if
he rolls a 6, he passes the die to his neighbour on the right; otherwise,
he keeps the die for the next turn.
The game ends when one player has both dice after they have been rolled
and passed; that player has then lost.
In a game with 100 players, what is the expected number of turns the game
lasts?
Answer: 7b87cd0a96f0f2f12f911cdc66608d95
Problem 228
===========
Let S[n] be the regular n-sided polygon – or shape – whose vertices v[k]
(k = 1,2,…,n) have coordinates:
x[k] = cos( ^2k-1/[n] ×180° )
y[k] = sin( ^2k-1/[n] ×180° )
The Minkowski sum, S+T, of two shapes S and T is the result of adding
every point in S to every point in T, where point addition is performed
coordinate-wise: (u, v) + (x, y) = (u+x, v+y).
For example, the sum of S[3] and S[4] is the six-sided shape shown in pink
below:
Visible links
p_228.png
Answer: 35d0195ddaf58e52e12400de1c9333d8
Problem 229
===========
n = a[1]^2 + b[1]^2
n = a[2]^2 + 2 b[2]^2
n = a[3]^2 + 3 b[3]^2
n = a[7]^2 + 7 b[7]^2,
Problem 230
===========
Example:
Now we use for A the first 100 digits of π behind the decimal point:
14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679
82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196 .
Answer: 040735038021ff4704bbd3a0964369ef
Problem 231
===========
Answer: ef8bc4d9a843e71126bd10b5065132a5
Problem 232
===========
Two players share an unbiased coin and take it in turns to play "The
Race". On Player 1's turn, he tosses the coin once: if it comes up Heads,
he scores one point; if it comes up Tails, he scores nothing. On Player
2's turn, she chooses a positive integer T and tosses the coin T times: if
it comes up all Heads, she scores 2^T-1 points; otherwise, she scores
nothing. Player 1 goes first. The winner is the first to 100 or more
points.
On each turn Player 2 selects the number, T, of coin tosses that maximises
the probability of her winning.
Give your answer rounded to eight decimal places in the form 0.abcdefgh .
Answer: c8d5b243aa6e6b507725766f7c197a1d
Problem 233
===========
Let f(N) be the number of points with integer coordinates that are on a
circle passing through (0,0), (N,0),(0,N), and (N,N).
What is the sum of all positive integers N ≤ 10^11 such that f(N) = 420 ?
Answer: 7e80b27798170abb493e3b4671bd82ca
Problem 234
===========
The sum of the semidivisible numbers not exceeding 15 is 30, the numbers
are 8, 10 and 12.
15 is not semidivisible because it is a multiple of both lps(15) = 3 and
ups(15) = 5.
As a further example, the sum of the 92 semidivisible numbers up to 1000
is 34825.
Problem 235
===========
Answer: 41b13508789be1001308e065d4f83ea2
Problem 236
===========
Suppliers 'A' and 'B' provided the following numbers of products for the
luxury hamper market:
Although the suppliers try very hard to ship their goods in perfect
condition, there is inevitably some spoilage - i.e. products gone bad.
• The five per-product spoilage rates for each supplier are equal to the
number of products gone bad divided by the number of products
supplied, for each of the five products in turn.
• The overall spoilage rate for each supplier is equal to the total
number of products gone bad divided by the total number of products
provided by that supplier.
To their surprise, the suppliers found that each of the five per-product
spoilage rates was worse (higher) for 'B' than for 'A' by the same factor
(ratio of spoilage rates), m>1; and yet, paradoxically, the overall
spoilage rate was worse for 'A' than for 'B', also by a factor of m.
There are thirty-five m>1 for which this surprising result could have
occurred, the smallest of which is 1476/1475.
Answer: 6e707fcffc510520d981ae16a29579bb
Problem 237
===========
Let T(n) be the number of tours over a 4 × n playing board such that:
p_237.gif
Answer: 0742988a3948491b15fb48e476c78a6a
Problem 238
===========
s[0] = 14025256
s[n+1] = s[n]^2 mod 20300713
For instance:
Note that substring 025 starting at position 3, has a sum of digits equal
to 7, but there was an earlier substring (starting at position 1) with a
sum of digits equal to 7, so p(7) = 1, not 3.
We can verify that, for 0 < k ≤ 10^3, ∑ p(k) = 4742.
Answer: 424ed6613a372ccb9a90dddb8961ca16
Problem 239
===========
Give your answer rounded to 12 places behind the decimal point in the form
0.abcdefghijkl.
Answer: 451fd2b8c19fbfec650a5c4699f6ef6e
Problem 240
===========
There are 1111 ways in which five 6-sided dice (sides numbered 1 to 6) can
be rolled so that the top three sum to 15. Some examples are:
D[1],D[2],D[3],D[4],D[5] = 4,3,6,3,5
D[1],D[2],D[3],D[4],D[5] = 4,3,3,5,6
D[1],D[2],D[3],D[4],D[5] = 3,3,3,6,6
D[1],D[2],D[3],D[4],D[5] = 6,6,3,3,3
In how many ways can twenty 12-sided dice (sides numbered 1 to 12) be
rolled so that the top ten sum to 70?
Answer: cb31a3106db3876e77cd160664cd683e
Problem 241
===========
Find the sum of all positive integers n ≤ 10^18 for which p(n) has the
form k + ^1⁄[2], where k is an integer.
Answer: 556bfef2cacd1eff8af9126c5c13dcbc
Problem 242
===========
Given the set {1,2,...,n}, we define f(n,k) as the number of its k-element
subsets with an odd sum of elements. For example, f(5,3) = 4, since the
set {1,2,3,4,5} has four 3-element subsets having an odd sum of elements,
i.e.: {1,2,4}, {1,3,5}, {2,3,4} and {2,4,5}.
When all three values n, k and f(n,k) are odd, we say that they make
an odd-triplet [n,k,f(n,k)].
Answer: ba73cb75365ddca8f94a23e3fedfb6de
Problem 243
===========
Answer: 531721a10786c5c2a444b474fcf039f9
Problem 244
===========
You probably know the game Fifteen Puzzle. Here, instead of numbered
tiles, we have seven red tiles and eight blue tiles.
(S) , (E)
┌──────┬─────┐
│L │76 │
├──────┼─────┤
│R │82 │
├──────┼─────┤
│U │85 │
├──────┼─────┤
│D │68 │
└──────┴─────┘
For the sequence LULUR given above, the checksum would be 19761398.
(S) , (T)
What is the sum of all checksums for the paths having the minimal length?
p_244_start.gif
p_244_example.gif
p_244_start.gif
p_244_target.gif
Answer: f8fd502ec1d0084a79d43d9dc5bd3a3d
Problem 245
===========
Find the sum of all composite integers 1 < n ≤ 2×10^11, for which C(n) is
a unit fraction.
Answer: 0ebeb502fb0bd7157609835d27c266bc
Problem 246
===========
For how many lattice points P is angle RPS greater than 45 degrees?
p_246_anim.gif
p_246_ellipse.gif
Answer: 94c521ffeb906391d161b66fec433827
Problem 247
===========
Let S[1] be the largest square that can fit under the curve.
Let S[2] be the largest square that fits in the remaining area, and so on.
Let the index of S[n] be the pair (left, below) indicating the number of
squares to the left of S[n] and the number of squares below S[n].
p_247_hypersquares.gif
Answer: 257956694e7665e3d512ad5b819ef79d
Problem 248
===========
Answer: b69a3ba674f6c7c5f2ce244f9e9cc873
Problem 249
===========
Let S = {2, 3, 5, ..., 4999} be the set of prime numbers less than 5000.
Answer: a470ee3ca52f2b68d7034e48b39b8b26
Problem 250
===========
Answer: 4a5614f3700956273fe0d271f921d5f4
Problem 251
===========
Find how many Cardano Triplets exist such that a+b+c ≤ 110,000,000.
p_251_cardano.gif
Answer: 9690315a09a4d9f58dcc19ad96e6e889
Problem 252
===========
As an example, the image below shows a set of twenty points and a few such
convex holes. The convex hole shown as a red heptagon has an area equal to
1049694.5 square units, which is the highest possible area for a convex
hole on the given set of points.
For our example, we used the first 20 points (T[2k−1], T[2k]), for
k = 1,2,…,20, produced with the pseudo-random number generator:
S[0] =[ ] 290797[ ]
S[n+1] =[ ] S[n]^2 mod 50515093
T[n] =[ ] ( S[n] mod 2000 ) − 1000^
What is the maximum area for a convex hole on the set containing the first
500 points in the pseudo-random sequence?
Specify your answer including one digit after the decimal point.
p_252_convexhole.gif
Answer: 53b1ced82e1b588d756750c4d2f77e0d
Problem 253
===========
Every night, the child's father has to pick up the pieces of the
caterpillar that have been scattered across the play room. He picks up the
pieces at random and places them in the correct order.
As the caterpillar is built up in this way, it forms distinct segments
that gradually merge together.
The number of segments starts at zero (no pieces placed), generally
increases up to about eleven or twelve, then tends to drop again before
finishing at a single segment (all pieces placed).
For example:
┌────────────┬───────────────┐
│Piece Placed│Segments So Far│
├────────────┼───────────────┤
│ 12 │ 1 │
├────────────┼───────────────┤
│ 4 │ 2 │
├────────────┼───────────────┤
│ 29 │ 3 │
├────────────┼───────────────┤
│ 6 │ 4 │
├────────────┼───────────────┤
│ 34 │ 5 │
├────────────┼───────────────┤
│ 5 │ 4 │
├────────────┼───────────────┤
│ 35 │ 4 │
├────────────┼───────────────┤
│ … │ … │
└────────────┴───────────────┘
┌────────┬─────────────┐
│ M │Possibilities│
├────────┼─────────────┤
│ 1 │ 512 │
├────────┼─────────────┤
│ 2 │ 250912 │
├────────┼─────────────┤
│ 3 │1815264 │
├────────┼─────────────┤
│ 4 │1418112 │
├────────┼─────────────┤
│ 5 │ 144000 │
└────────┴─────────────┘
The most likely value of M for a forty-piece caterpillar is 11; but what
is the average value of M?
Answer: 228de0a37019fd7c7051029f3d126422
Problem 254
===========
Define f(n) as the sum of the factorials of the digits of n. For example,
f(342) = 3! + 4! + 2! = 32.
Answer: 936014adf2de65d41979ad900325e485
Problem 255
===========
Note: The symbols ⌊x⌋ and ⌈x⌉ represent the floor function and ceiling
function respectively.
p_255_Heron.gif
p_255_Example.gif
Answer: 12be028b156b49faa1137febda940ab5
Problem 256
===========
Tatami are rectangular mats, used to completely cover the floor of a room,
without overlap.
Assuming that the only type of available tatami has dimensions 1×2, there
are obviously some limitations for the shape and size of the rooms that
can be covered.
There is one rule to follow when laying out tatami: there must be no
points where corners of four different mats meet.
For example, consider the two arrangements below for a 4×4 room:
The arrangement on the left is acceptable, whereas the one on the right is
not: a red "X" in the middle, marks the point where four tatami meet.
p_256_tatami3.gif
Answer: ef8eb0c177d00a5b80e1723786a22698
Problem 257
===========
The segments EF, EG and FG partition the triangle ABC into four smaller
triangles: AEG, BFE, CGF and EFG.
It can be proven that for each of these four triangles the ratio
area(ABC)/area(subtriangle) is rational.
However, there exist triangles for which some or all of these ratios are
integral.
How many triangles ABC with perimeter≤100,000,000 exist so that the ratio
area(ABC)/area(AEG) is integral?
p_257_bisector.gif
Answer: 3ba58bde91c83c98904050d90e466ce2
Problem 258
===========
Answer: 18eca0138f3acbde20dcc24ed06627ea
Problem 259
===========
• Uses the digits 1 through 9, in that order and exactly once each.
• Any successive digits can be concatenated (for example, using the
digits 2, 3 and 4 we obtain the number 234).
• Only the four usual binary arithmetic operations (addition,
subtraction, multiplication and division) are allowed.
• Each operation can be used any number of times, or not at all.
• Unary minus is not allowed.
• Any number of (possibly nested) parentheses may be used to define the
order of operations.
Answer: 771828a57c269d873335c9091af78f76
Problem 260
===========
A winning configuration is one where the first player can force a win.
For example, (0,0,13), (0,11,11) and (5,5,5) are winning configurations
because the first player can immediately remove all stones.
A losing configuration is one where the second player can force a win, no
matter what the first player does.
For example, (0,1,2) and (1,3,3) are losing configurations: any legal move
leaves a winning configuration for the second player.
Answer: cab69719e6968409ba167707a09875cb
Problem 261
===========
Answer: d45ddf64010ed143228a6a6b84837de9
Problem 262
===========
p_262_formula1.gif
Answer: a5921e175a44d31e7f82f7f9a61a36af
Problem 263
===========
an engineers’ paradise.
Answer: 8fe3eb7196c69a080740e076cff9b4a1
Problem 264
===========
p_264_TriangleCentres.gif
Answer: 287514a045a38be0a75a1786694c77ee
Problem 265
===========
2^N binary digits can be placed in a circle so that all the N-digit
clockwise subsequences are distinct.
For N=3, two such circular arrangements are possible, ignoring rotations:
Calling S(N) the sum of the unique numeric representations, we can see
that S(3) = 23 + 29 = 52.
Find S(5).
p_265_BinaryCircles.gif
Answer: c25cebbc8dce4bdcf96cb395a11afcc3
Problem 266
===========
Answer: 32da1d501e539ab509f104e2db68d57a
Problem 267
===========
Your return is double your bet for heads and you lose your bet for tails.
For example, if f = 1/4, for the first toss you bet £0.25, and if heads
comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if
the second toss is tails, you have £1.125.
All computations are assumed to be exact (no rounding), but give your
answer rounded to 12 digits behind the decimal point in the form
0.abcdefghijkl.
Answer: b8dd3306c2c64eacb0ac36b414892edb
Problem 268
===========
It can be verified that there are 23 positive integers less than 1000 that
are divisible by at least four distinct primes less than 100.
Find how many positive integers less than 10^16 are divisible by at least
four distinct primes less than 100.
Answer: 6f84b20c10311cb24a824416a3c3e0a4
Problem 269
===========
What is Z(10^16)?
Answer: f7ba868cb52a9b9c7e58b1b92e230be8
Problem 270
===========
• We only make straight cuts between two points lying on different sides
of the square, and having integer coordinates.
• Two cuts cannot cross, but several cuts can meet at the same border
point.
• Proceed until no more legal cuts can be made.
p_270_CutSquare.gif
Answer: 2a592dfd1e9e3e9e38578affa7c72605
Problem 271
===========
For a positive number n, define S(n) as the sum of the integers x, for
which 1<x<n and
x^3≡1 mod n.
When n=91, there are 8 possible values for x, namely : 9, 16, 22, 29, 53,
74, 79, 81.
Thus, S(91)=9+16+22+29+53+74+79+81=363.
Find S(13082761331670030).
Answer: c4157aab542bd0dfa465c890e1286cc5
Problem 272
===========
For a positive number n, define C(n) as the number of the integers x, for
which 1<x<n and
x^3≡1 mod n.
When n=91, there are 8 possible values for x, namely : 9, 16, 22, 29, 53,
74, 79, 81.
Thus, C(91)=8.
Find the sum of the positive numbers n≤10^11 for which C(n)=242.
Answer: d84d2020055b3e8867dc359e739e0312
Problem 273
===========
We call S(N) the sum of the values of a of all solutions of a^2 + b^2 = N,
0 ≤ a ≤ b, a, b and N integer.
Thus S(65) = 1 + 4 = 5.
Find ∑S(N), for all squarefree N only divisible by primes of the form 4k+1
with 4k+1 < 150.
Answer: 2b03731e58e9d60e559ee5fdce4f0d14
Problem 274
===========
(When n is much larger than p, f(n) will be less than n and repeated
application of f provides a multiplicative divisibility test for p.)
For example, the divisibility multiplier for 113 is 34.
f(76275) = 7627 + 5 * 34 = 7797 : 76275 and 7797 are both divisible by 113
f(12345) = 1234 + 5 * 34 = 1404 : 12345 and 1404 are both not divisible by
113
The sum of the divisibility multipliers for the primes that are coprime to
10 and less than 1000 is 39517. What is the sum of the divisibility
multipliers for the primes that are coprime to 10 and less than 10^7?
Answer: ffd68ca67b9c3ea2653d375051e70288
Problem 275
===========
There are 964 balanced sculptures of order 10 and 360505 of order 15.
How many balanced sculptures are there of order 18?
p_275_sculptures2.gif
Answer: a2a192f9790dcbfe4b450a82c4461d4a
Problem 276
===========
Answer: 29ae64e74ebfdf459dac56786e95c5d5
Problem 277
===========
A modified Collatz sequence of integers is obtained from a starting value
a[1] in the following way:
Of course, there are other sequences that begin with that same sequence
"DdDddUUdDD....".
For instance, if a[1]=1004064, then the sequence is
DdDddUUdDDDdUDUUUdDdUUDDDUdDD.
In fact, 1004064 is the smallest possible a[1] > 10^6 that begins with the
sequence DdDddUUdDD.
What is the smallest a[1] > 10^15 that begins with the sequence
"UDDDUdddDDUDDddDdDddDDUDDdUUDd"?
Answer: 9508afff135320c18d82c93a8b70cd11
Problem 278
===========
Given the values of integers 1 < a[1] < a[2] <... < a[n], consider the
linear combination
q[1]a[1] + q[2]a[2] + ... + q[n]a[n] = b, using only integer values q[k] ≥
0.
Note that for a given set of a[k], it may be that not all values of b are
possible.
For instance, if a[1] = 5 and a[2] = 7, there are no q[1] ≥ 0 and q[2] ≥ 0
such that b could be
1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 or 23.
In fact, 23 is the largest impossible value of b for a[1] = 5 and a[2] =
7.
We therefore call f(5, 7) = 23.
Similarly, it can be shown that f(6, 10, 15)=29 and f(14, 22, 77) = 195.
Find ∑ f(p*q,p*r,q*r), where p, q and r are prime numbers and p < q < r <
5000.
Answer: 7e680606b5e9890a19894dbdbbbd102a
Problem 279
===========
How many triangles are there with integral sides, at least one integral
angle (measured in degrees), and a perimeter that does not exceed 10^8?
Answer: 1f51455a8180fdeeb21285dfb6cba45f
Problem 280
===========
A laborious ant walks randomly on a 5x5 grid. The walk starts from the
central square. At each step, the ant moves to an adjacent square at
random, without leaving the grid; thus there are 2, 3 or 4 possible moves
at each step depending on the ant's position.
At the start of the walk, a seed is placed on each square of the lower
row. When the ant isn't carrying a seed and reaches a square of the lower
row containing a seed, it will start to carry the seed. The ant will drop
the seed on the first empty square of the upper row it eventually reaches.
What's the expected number of steps until all seeds have been dropped in
the top row?
Give your answer rounded to 6 decimal places.
Answer: 27f07f04d1908e5ce4fa6eac09881cc2
Problem 281
===========
You are given a pizza (perfect circle) that has been cut into m·n equal
pieces and you want to have exactly one topping on each slice.
Let f(m,n) denote the number of ways you can have toppings on the pizza
with m different toppings (m ≥ 2), using each topping on exactly n slices
(n ≥ 1).
Reflections are considered distinct, rotations are not.
p_281_pizza.gif
Answer: ceee6ced9d64aad844310c8ce2aae2b7
Problem 282
===========
For non-negative integers m, n, the Ackermann function A(m, n) is defined
as follows:
p_282_formula.gif
Answer: a1cc665e127af4e907e13087ee777bd5
Problem 283
===========
Consider the triangle with sides 6, 8 and 10. It can be seen that the
perimeter and the area are both equal to 24. So the area/perimeter ratio
is equal to 1.
Consider also the triangle with sides 13, 14 and 15. The perimeter equals
42 while the area is equal to 84. So for this triangle the area/perimeter
ratio is equal to 2.
Find the sum of the perimeters of all integer sided triangles for which
the area/perimeter ratios are equal to positive integers not exceeding
1000.
Answer: 08afda4bc05c8f3ef71c9ffea1ddc0c8
Problem 284
===========
For 1 ≤ n ≤ 9, the sum of the digits of all the n-digit steady squares in
the base 14 numbering system is 2d8 (582 decimal). Steady squares with
leading 0's are not allowed.
Find the sum of the digits of all the n-digit steady squares in the base
14 numbering system for
1 ≤ n ≤ 10000 (decimal) and give your answer in the base 14 system using
lower case letters where necessary.
Answer: aff724582e583649876f518f9b340a69
Problem 285
===========
Answer: bbae95d0ce2999cae57782c3746aecb6
Problem 286
===========
Barbara is a mathematician and a basketball player. She has found that the
probability of scoring a point when shooting from a distance x is exactly
(1 - ^x/[q]), where q is a real constant greater than 50.
Answer: cc5a1ef0deabf698733bcef4f1149498
Problem 287
===========
Consider the following 4×4 image (colored marks denote places where a
split can occur):
For a positive integer N, define D[N] as the 2^N×2^N image with the
following coloring scheme:
p_287_quadtree.gif
Answer: 6c2beec8a6c0bc788d5e45c317b0d7ca
Problem 288
===========
S[0] = 290797
S[n+1] = S[n]^2 mod 50515093
T[n] = S[n] mod p
Answer: 192bf4aa33ea85e922d583f60fe99955
Problem 289
===========
Let C(x,y) be a circle passing through the points (x, y), (x, y+1),
(x+1, y) and (x+1, y+1).
An Eulerian cycle on E(m,n) is a closed path that passes through each arc
exactly once.
Many such paths are possible on E(m,n), but we are only interested in
those which are not self-crossing: A non-crossing path just touches itself
at lattice points, but it never crosses itself.
p_289_euler.gif
Answer: 9fa32696df356b3d41faa7dd278c88a9
Problem 290
===========
How many integers 0 ≤ n < 10^18 have the property that the sum of the
digits of n equals the sum of digits of 137n?
Answer: 8246684fec8ece9f0ee3c9898c8c9d6a
Problem 291
===========
p_291_formula.gif
Answer: 15d4b4d97452ca7d219e3fa72f6b7aef
Problem 292
===========
You are given that P(4) = 1, P(30) = 3655 and P(60) = 891045.
Find P(120).
Answer: 27f50f02ef10f170379b144435e0144b
Problem 293
===========
For example, N=630 is admissible since it is even and its distinct prime
factors are the consecutive primes 2,3,5 and 7.
The next prime number after 631 is 641; hence, the pseudo-Fortunate number
for 630 is M=11.
It can also be seen that the pseudo-Fortunate number for 16 is 3.
Answer: db116b39f7a3ac5366079b1d9fe249a5
Problem 294
===========
For a positive integer k, define d(k) as the sum of the digits of k in its
usual decimal representation.Thus d(42) = 4+2 = 6.
• k is divisible by 23 and
• d(k) = 23.
Answer: aefe049404a284c7d27fab3887c6c4a2
Problem 295
===========
We call the convex area enclosed by two circles a lenticular hole if:
The circles C[0], C[1] and C[2] are drawn in the picture below.
C[0] and C[1] form a lenticular hole, as well as C[0] and C[2].
Let L(N) be the number of distinct lenticular pairs (r[1], r[2]) for which
0 < r[1] ≤ r[2] ≤ N.
We can verify that L(10) = 30 and L(100) = 3442.
Answer: 5beaace6425205fe879116ee07dae961
Problem 296
===========
How many triangles ABC with a perimeter not exceeding 100 000 exist such
that BE has integral length?
Answer: 45986a4405b2dd6c163516319e0c4a1b
Problem 297
===========
For any integer n>0, let z(n) be the number of terms in the Zeckendorf
representation of n.
Thus, z(5) = 1, z(14) = 2, z(100) = 3 etc.
Also, for 0<n<10^6, ∑ z(n) = 7894453.
Answer: d3fd75f5447698748a826562750a1986
Problem 298
===========
Both players start with empty memories. Both players always add new missed
numbers to their memory but use a different strategy in deciding which
number to remove:
Larry's strategy is to remove the number that hasn't been called in the
longest time.
Robin's strategy is to remove the number that's been in the memory the
longest time.
Example game:
Answer: d078fd564995aa2a813a29f44ad79611
Problem 299
===========
Four points with integer coordinates are selected:
A(a, 0), B(b, 0), C(0, c) and D(0, d), with 0 < a < b and 0 < c < d.
Point P, also with integer coordinates, is chosen on the line AC so that
the three triangles ABP, CDP and BDP are all similar.
It is easy to prove that the three triangles can be similar, only if a=c.
So, given that a=c, we are looking for triplets (a,b,d) such that at least
one point P (with integer coordinates) exists on AC, making the three
triangles ABP, CDP and BDP all similar.
If b+d < 100, there are 92 distinct triplets (a,b,d) such that point P
exists.
If b+d < 100 000, there are 320471 distinct triplets (a,b,d) such that
point P exists.
If b+d < 100 000 000, how many distinct triplets (a,b,d) are there such
that point P exists?
p_299_ThreeSimTri.gif
Answer: fb8f093361a6db56c8a1d1661ab229cd
Problem 300
===========
When one encounters these strings in nature, they are always folded in
such a way that the number of H-H contact points is as large as possible,
since this is energetically advantageous.
As a result, the H-elements tend to accumulate in the inner part, with the
P-elements on the outside.
Natural proteins are folded in three dimensions of course, but we will
only consider protein folding in two dimensions.
The figure below shows two possible ways that our example protein could be
folded (H-H contact points are shown with red dots).
The folding on the left has only six H-H contact points, thus it would
never occur naturally.
On the other hand, the folding on the right has nine H-H contact points,
which is optimal for this string.
Assuming that H and P elements are equally likely to occur in any position
along the string, the average number of H-H contact points in an optimal
folding of a random protein string of length 8 turns out to be
850 / 2^8=3.3203125.
p_300_protein.gif
Answer: 5a0d6315bc18279c46a1fb8cbd2f16b5
Problem 301
===========
Nim is a game played with heaps of stones, where two players take it in
turn to remove any number of stones from any heap until no stones remain.
• zero if, with perfect strategy, the player about to move will
eventually lose; or
• non-zero if, with perfect strategy, the player about to move will
eventually win.
For example X(1,2,3) = 0 because, no matter what the current player does,
his opponent can respond with a move that leaves two heaps of equal size,
at which point every move by the current player can be mirrored by his
opponent until no stones remain; so the current player loses. To
illustrate:
- current player moves to (1,2,1)
- opponent moves to (1,0,1)
- current player moves to (0,0,1)
- opponent moves to (0,0,0), and so wins.
Answer: f47b7d975a5ebd3b66af0968ef5e1cdb
Problem 302
===========
There are 7 Strong Achilles numbers below 10^4 and 656 below 10^8.
Answer: 1ea8b8d64cead5149721a128b0de378c
Problem 303
===========
Also, .
Find .
Answer: b904a0b3d922e628a828e744ee7d3a60
Problem 304
===========
For any positive integer n the function next_prime(n) returns the smallest
prime p
such that p>n.
Find ∑b(n) for 1≤n≤100 000. Give your answer mod 1234567891011.
Answer: 499427a3e4bf9ad34a6df3056604b4c1
Problem 305
===========
It's easy to see that any number will show up an infinite number of times
in S.
Answer: 9def85298f598867d361e4afca8cdd96
Problem 306
===========
Two players start with a strip of n white squares and they take alternate
turns.
On each turn, a player picks two contiguous white squares and paints them
black.
The first player who cannot make a move loses.
So, for 1 ≤ n ≤ 5, there are 3 values of n for which the first player can
force a win.
Similarly, for 1 ≤ n ≤ 50, there are 40 values of n for which the first
player can force a win.
For 1 ≤ n ≤ 1 000 000, how many values of n are there for which the first
player can force a win?
p_306_pstrip.gif
Answer: 394d602ba21e30693db90c9ecd4bd3a2
Problem 307
===========
Let p(k,n) represent the probability that there is a chip with at least 3
defects.
For instance p(3,7) ≈ 0.0204081633.
Find p(20 000, 1 000 000) and give your answer rounded to 10 decimal
places in the form 0.abcdefghij
Answer: 0c49094fa750365e13bb20ec4a158b6d
Problem 308
===========
For example, one of the Fractran programs that John Horton Conway wrote
for prime-generation consists of the following 14 fractions:
17 , 78 , 19 , 23 , 29 , 77 , 95 , 77 , 1 , 11 , 13 , 15 , 1 , 55 .
91 85 51 38 33 29 23 19 17 13 11 2 7 1
The powers of 2 that appear in this sequence are 2^2, 2^3, 2^5, ...
It can be shown that all the powers of 2 in this sequence have prime
exponents and that all the primes appear as exponents of powers of 2, in
proper order!
If someone uses the above Fractran program to solve Project Euler Problem
7 (find the 10001^st prime), how many iterations would be needed until the
program produces 2^10001st prime ?
Answer: 43e736dfc6478a52653814248a71771d
Problem 309
===========
In the classic "Crossing Ladders" problem, we are given the lengths x and
y of two ladders resting on the opposite walls of a narrow, level street.
We are also given the height h above the street where the two ladders
cross and we are asked to find the width of the street (w).
Here, we are only concerned with instances where all four variables are
positive integers.
For example, if x = 70, y = 119 and h = 30, we can calculate that w = 56.
In fact, for integer values x, y, h and 0 < x < y < 200, there are only
five triplets (x,y,h) producing integer solutions for w:
(70, 119, 30), (74, 182, 21), (87, 105, 35), (100, 116, 35) and (119, 175,
40).
For integer values x, y, h and 0 < x < y < 1 000 000, how many triplets
(x,y,h) produce integer solutions for w?
p_309_ladders.gif
Answer: 0875415a84bfe8bc237dcfc6b440d263
Problem 310
===========
Find the number of losing positions for the next player if 0≤a≤b≤c≤100
000.
Answer: 6b94f848996393eef163add4d17360c7
Problem 311
===========
ABCD is a convex, integer sided quadrilateral with 1 ≤ AB < BC < CD < AD.
BD has integer length. O is the midpoint of BD. AO has integer length.
We'll call ABCD a biclinic integral quadrilateral if AO = CO ≤ BO = DO.
Problem 312
===========
Let C(n) be the number of cycles that pass exactly once through all the
vertices of S[n].
For example, C(3) = 8 because eight such cycles can be drawn on S[3], as
shown below:
p_312_sierpinskyAt.gif
p_312_sierpinsky8t.gif
Answer: 535113d1a81f421fe814d48205dac570
Problem 313
===========
Let S(m,n) represent the minimum number of moves to complete the game on
an m by n grid. For example, it can be verified that S(5,4) = 25.
There are exactly 5482 grids for which S(m,n) = p^2, where p < 100 is
prime.
How many grids does S(m,n) = p^2, where p < 10^6 is prime?
p_313_sliding_game_1.gif
p_313_sliding_game_2.gif
Answer: 2468d42fa1c7f61547ce71c9826218ea
Problem 314
===========
The moon has been opened up, and land can be obtained for free, but there
is a catch. You have to build a wall around the land that you stake out,
and building a wall on the moon is expensive. Every country has been
allotted a 500 m by 500 m square area, but they will possess only that
area which they wall in. 251001 posts have been placed in a rectangular
grid with 1 meter spacing. The wall must be a closed series of straight
lines, each line running from post to post.
The bigger countries of course have built a 2000 m wall enclosing the
entire 250 000 m^2 area. The [1]Duchy of Grand Fenwick, has a tighter
budget, and has asked you (their Royal Programmer) to compute what shape
would get best maximum enclosed-area/wall-length ratio.
However, if you cut off from the square four triangles with sides 75 m, 75
m and 75√2 m the total area becomes 238750 m^2 and the perimeter becomes
1400+300√2 m. So this gives an enclosed-area/wall-length ratio of 130.87,
which is significantly better.
Visible links
1. http://en.wikipedia.org/wiki/Grand_Fenwick
p_314_landgrab.gif
Answer: aa457cae6f67945d50683a85a9b70230
Problem 315
===========
Sam and Max are asked to transform two digital clocks into two "digital
root" clocks.
A digital root clock is a digital clock that calculates digital roots step
by step.
When a clock is fed a number, it will show it and then it will start the
calculation, showing all the intermediate values until it gets to the
result.
For example, if the clock is fed the number 137, it will show: "137" →
"11" → "2" and then it will go black, waiting for the next number.
The clocks consume energy only when segments are turned on/off.
To turn on a "2" will cost 5 transitions, while a "7" will cost only 4
transitions.
Sam's clock is fed e.g. number 137: the clock shows "137", then the panel
is turned off, then the next number ("11") is turned on, then the panel is
turned off again and finally the last number ("2") is turned on and, after
some time, off.
For the example, with number 137, Sam's clock requires:
Max's clock works differently. Instead of turning off the whole panel, it
is smart enough to turn off only those segments that won't be needed for
the next number.
For number 137, Max's clock requires:
p_315_clocks.gif
Answer: 79b587f9c25a72dbe95428e283628421
Problem 316
===========
p_316_decexp1.gif
p_316_decexp2.gif
p_316_decexp3.gif
Answer: 2495e8f6e9d4cdadbf0411144e7180b9
Problem 317
===========
Find the volume (in m^3) of the region through which the fragments move
before reaching the ground. Give your answer rounded to four decimal
places.
Answer: b0e2bec93bfe598ade5d3d1141f76bdd
Problem 318
===========
It looks like that the number of consecutive nines at the beginning of the
fractional part of these powers is non-decreasing.
In fact it can be proven that the fractional part of (√2+√3)^2n approaches
1 for large n.
Consider all real numbers of the form √p+√q with p and q positive integers
and p<q, such that the fractional part of (√p+√q)^2n approaches 1 for
large n.
Answer: de358f1c4d6e30c1a4f82c8bc5cedf2d
Problem 319
===========
• x[1] = 2
• for all 1 < i ≤ n : x[i-1] < x[i]
• for all i and j with 1 ≤ i, j ≤ n : (x[i]) ^ j < (x[j] + 1)^i
Answer: d346ab7d128ee0402820edf5fe4aed30
Problem 320
===========
S(1000)=614538266565663.
Answer: 8426f939c3ee410a8c4d43886ef77ccb
Problem 321
===========
A counter can move from one square to the next (slide) or can jump over
another counter (hop) as long as the square next to that counter is
unoccupied.
p_321_swapping_counters_1.gif
p_321_swapping_counters_2.gif
Answer: 6d87412130312b01a999225a5fe689b1
Problem 322
===========
Let T(m, n) be the number of the binomial coefficients ^iC[n] that are
divisible by 10 for n ≤ i < m(i, m and n are positive integers).
You are given that T(10^9, 10^7-10) = 989697000.
Answer: a75af9d717fa592487fb45e7552204a8
Problem 323
===========
• x[0] = 0 and
• x[i] = x[i-1] | y[i-1], for i > 0. ( | is the bitwise-OR operator)
It can be seen that eventually there will be an index N such that x[i] =
2^32 -1 (a bit-pattern of all ones) for all i ≥ N.
Find the expected value of N.
Give your answer rounded to 10 digits after the decimal point.
Answer: c8f8a7ab17a87f1b17a1f4a86c984ea7
Problem 324
===========
Let f(n) represent the number of ways one can fill a 3×3×n tower with
blocks of 2×1×1.
You're allowed to rotate the blocks in any way you like; however,
rotations, reflections etc of the tower itself are counted as distinct.
Answer: b8d91b06d43a2ef98a6fcb0be4a6d617
Problem 325
===========
A game is played with two piles of stones and two players. At her turn, a
player removes a number of stones from the larger pile. The number of
stones she removes must be a positive multiple of the number of stones in
the smaller pile.
The player taking all the stones from a pile wins the game.
A winning configuration is one where the first player can force a win. For
example, (1,5), (2,6) and (3,12) are winning configurations because the
first player can immediately remove all stones in the second pile.
A losing configuration is one where the second player can force a win, no
matter what the first player does. For example, (2,3) and (3,4) are losing
configurations: any legal move leaves a winning configuration for the
second player.
Problem 326
===========
It can be seen that f(10,10)=4 with the pairs (3,3), (5,5), (7,9) and
(9,10).
Find f(10^12,10^6).
p_326_formula1.gif
p_326_formula2.gif
Answer: d95dff1a5ceee0064993d98defdd603e
Problem 327
===========
Each door is operated by a security card. Once you enter a room the door
automatically closes and that security card cannot be used again. A
machine at the start will dispense an unlimited number of cards, but each
room (including the starting room) contains scanners and if they detect
that you are holding more than three security cards or if they detect an
unattended security card on the floor, then all the doors will become
permanently locked. However, each room contains a box where you may safely
store any number of security cards for use at a later stage.
If you simply tried to travel through the rooms one at a time then as you
entered room 3 you would have used all three cards and would be trapped in
that room forever!
However, if you make use of the storage boxes, then escape is possible.
For example, you could enter room 1 using your first card, place one card
in the storage box, and use your third card to exit the room back to the
start. Then after collecting three more cards from the dispensing machine
you could use one to enter room 1 and collect the card you placed in the
box a moment ago. You now have three cards again and will be able to
travel through the remaining three doors. This method allows you to travel
through all three rooms using six security cards in total.
Let C be the maximum number of cards which can be carried at any time.
Let R be the number of rooms to travel through.
Let M(C,R) be the minimum number of cards required from the dispensing
machine to travel through R rooms carrying up to a maximum of C cards at
any time.
p_327_rooms_of_doom.gif
Answer: 2cd4c0ad8a00c5be99802188ee2628fb
Problem 328
===========
We are trying to find a hidden number selected from the set of integers
{1, 2, ..., n} by asking questions. Each number (question) we ask, has a
cost equal to the number asked and we get one of three possible answers:
Given the value of n, an optimal strategy minimizes the total cost (i.e.
the sum of all the questions asked) for the worst possible case. E.g.
If n=3, the best we can do is obviously to ask the number "2". The answer
will immediately lead us to find the hidden number (at a total cost = 2).
We can improve considerably the worst-case cost for n=8, by asking "5" as
our first question.
If we are told that the hidden number is higher than 5, our second
question will be "7", then we'll know for certain what the hidden number
is (for a total cost of 5+7=12).
If we are told that the hidden number is lower than 5, our second question
will be "3" and if the hidden number is lower than 3 our third question
will be "1", giving a total cost of 5+3+1=9.
Since 12>9, the worst-case cost for this strategy is 12. That's better
than what we achieved previously with the "binary search" strategy; it is
also better than or equal to any other strategy.
So, in fact, we have just described an optimal strategy for n=8.
Find C(n).
p_328_sum1.gif
p_328_sum2.gif
Answer: 92a3220ad5b17a562c039e6e93d6df90
Problem 329
===========
Given that the frog's starting position is random with the same
probability for every square, and given that she listens to his first 15
croaks, what is the probability that she hears the sequence
PPPPNNPPPNPPNPN?
Answer: e392a8b1b053c83e68663e08456bb392
Problem 330
===========
For example,
a(0) = 1 + 1 + 1 + ... = e − 1
1! 2! 3!
a(1) = e − 1 + 1 + 1 + ... = 2e − 3
1! 2! 3!
a(2) = 2e − 3 + e − 1 + 1 + ... = 7 e − 6
1! 2! 3! 2
Find A(10^9) + B(10^9) and give your answer mod 77 777 777.
p_330_formula.gif
Answer: d385d3fe0995b48a782a91477525b154
Problem 331
===========
N×N disks are placed on a square game board. Each disk has a black side
and white side.
At each turn, you may choose a disk and flip all the disks in the same row
and the same column as this disk: thus 2×N-1 disks are flipped. The game
ends when all disks show their white side. The following example shows a
game on a 5×5 board.
The bottom left disk on the N×N board has coordinates (0,0);
the bottom right disk has coordinates (N-1,0) and the top left disk has
coordinates (0,N-1).
Let T(N) be the minimal number of turns to finish a game starting from
configuration C[N] or 0 if configuration C[N] is unsolvable.
We have shown that T(5)=3. You are also given that T(10)=29 and T(1
000)=395253.
Find .
p_331_crossflips3.gif
p_331_crossflips1.gif
p_331_crossflips2.gif
Answer: b609ccc578e71db9de0524fff94e1b70
Problem 332
===========
Let C(r) be the sphere with the centre (0,0,0) and radius r.
Let Z(r) be the set of points on the surface of C(r) with integer
coordinates.
Let T(r) be the set of spherical triangles with vertices in
Z(r).Degenerate spherical triangles, formed by three points on the same
great arc, are not included in T(r).
Let A(r) be the area of the smallest spherical triangle in T(r).
p_332_spherical.jpg
p_332_sum.gif
Answer: c2ae53ebfb15db373cfe5d71078ea1ca
Problem 333
===========
All positive integers can be partitioned in such a way that each and every
term of the partition can be expressed as 2^ix3^j, where i,j ≥ 0.
Let's consider only those such partitions where none of the terms can
divide any of the other terms.
For example, the partition of 17 = 2 + 6 + 9 = (2^1x3^0 + 2^1x3^1 +
2^0x3^2) would not be valid since 2 can divide 6. Neither would the
partition 17 = 16 + 1 = (2^4x3^0 + 2^0x3^0) since 1 can divide 16. The
only valid partition of 17 would be 8 + 9 = (2^3x3^0 + 2^0x3^2).
Many integers have more than one valid partition, the first being 11
having the following two partitions.
11 = 2 + 9 = (2^1x3^0 + 2^0x3^2)
11 = 8 + 3 = (2^3x3^0 + 2^0x3^1)
Let's consider only the prime integers q which would have a single valid
partition such as P(17).
The sum of the primes q <100 such that P(q)=1 equals 233.
Answer: 8408ff3a470a94dbfca1819249eb547d
Problem 334
===========
t[0] = 123456.
The first two terms of the last sequence are b[1] = 289 and b[2] = 145.
If we start with b[1] and b[2] beans in two adjacent bowls, 3419100 moves
would be required to finish the game.
Consider now 1500 adjacent bowls containing b[1], b[2],..., b[1500] beans
respectively, all other bowls being empty. Find how many moves it takes
before the game ends.
p_334_beans.gif
p_334_cases.gif
p_334_lfloor.gif
p_334_rfloor.gif
p_334_oplus.gif
Answer: 71851da3058acf6b74e90251bdf4aa8f
Problem 335
===========
Whenever Peter feels bored, he places some bowls, containing one bean
each, in a circle. After this, he takes all the beans out of a certain
bowl and drops them one by one in the bowls going clockwise. He repeats
this, starting from the bowl he dropped the last bean in, until the
initial situation appears again. For example with 5 bowls he acts as
follows:
Let M(x) represent the number of moves required to return to the initial
situation, starting with x bowls. Thus, M(5) = 15. It can also be verified
that M(100) = 10920.
p_335_mancala.gif
p_335_sum.gif
Answer: 9a519cfa0ebdd4d1dd318f14b5799eea
Problem 336
===========
However, Simple Simon, the train driver, is not known for his efficiency,
so he always solves the problem by initially getting carriage A in the
correct place, then carriage B, and so on.
Using four carriages, the worst possible arrangements for Simon, which we
shall call maximix arrangements, are DACB and DBAC; each requiring him
five rotations (although, using the most efficient approach, they could be
solved using just three rotations). The process he uses for DACB is shown
below.
p_336_maximix.gif
Answer: 7968e48fc692ce25bf7f5494f4ab6814
Problem 337
===========
• a[1] = 6
• for all 1 ≤ i < n : φ(a[i]) < φ(a[i+1]) < a[i] < a[i+1] ^1
Answer: a60bbbe1b90254043fb92820492a2f96
Problem 338
===========
For a pair w and h, let F(w,h) be the number of distinct rectangles that
can be made from a sheet with dimensions w × h .
For example, F(2,1) = 0, F(2,2) = 1, F(9,4) = 3 and F(9,8) = 2.
Note that rectangles congruent to the initial one are not counted in
F(w,h).
Note also that rectangles with dimensions w × h and dimensions h × w are
not considered distinct.
For an integer N, let G(N) be the sum of F(w,h) for all pairs w and h
which satisfy 0 < h ≤ w ≤ N.
We can verify that G(10) = 55, G(10^3) = 971745 and G(10^5) = 9992617687.
p_338_gridpaper.gif
Answer: 99f4f702713f3422ced01dd7d3d79644
Problem 339
===========
"And he came towards a valley, through which ran a river; and the borders
of the valley were wooded, and on each side of the river were level
meadows. And on one side of the river he saw a flock of white sheep, and
on the other a flock of black sheep. And whenever one of the white sheep
bleated, one of the black sheep would cross over and become white; and
when one of the black sheep bleated, one of the white sheep would cross
over and become black."
[1]en.wikisource.org
You are given that E(5) = 6.871346 rounded to 6 places behind the decimal
point.
Find E(10 000) and give your answer rounded to 6 places behind the decimal
point.
Visible links
1. http://en.wikisource.org/wiki/The_Mabinogion/Peredur_the_Son_of_Evrawc
Answer: 0be02210b2d2212d37d026478093c457
Problem 340
===========
For example, if a = 50, b = 2000 and c = 40, then F(0) = 3240 and F(2000)
= 2040.
Also, S(50, 2000, 40) = 5204240.
p_340_formula.gif
Answer: fc838afe9ecde39bbe230923d7b50775
Problem 341
===========
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 …
G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 …
Answer: 7c163c3b4886943667b5c89db0a6cd02
Problem 342
===========
Answer: 0e9add0383d4116c7c5cb3dc73fc0536
Problem 343
===========
So f(20) = 6.
Answer: 0e10bd111425ad8e1343ac79dac7bb0e
Problem 344
===========
On a strip of squares a number of coins are placed, at most one coin per
square. Only one coin, called the silver dollar, has any value. Two
players take turns making moves. At each turn a player must make either a
regular or a special move.
A regular move consists of selecting one coin and moving it one or more
squares to the left. The coin cannot move out of the strip or jump on or
over another coin.
Alternatively, the player can choose to make the special move of pocketing
the leftmost coin rather than making a regular move. If no regular moves
are possible, the player is forced to pocket the leftmost coin.
Find W(1 000 000, 100) modulo the semiprime 1000 036 000 099 (= 1 000 003
· 1 000 033).
p_344_silverdollar.gif
Answer: 38e7b980b38fcac89b3e267e328cd292
Problem 345
===========
We define the Matrix Sum of a matrix as the maximum sum of matrix elements
with each element being the only one in his row and column. For example,
the Matrix Sum of the matrix below equals 3315 ( = 863 + 383 + 343 + 959 +
767):
7 53 183 439 863 497 383 563 79 973 287 63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463 29 23 487 463 993 119 883 327 493 423 159 743
217 623 3 399 853 407 103 983 89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915 45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601 95 973
445 721 11 525 473 65 511 164 138 672 18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513 17 901 711 993 293 157 274 94 192 156 574
34 124 4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615 77 281 613 459 205 380 274 302 35 805
Answer: cf3b784c8593890043b17e24088125d4
Problem 346
===========
Answer: a17874b5a9ec9d7fc8c6489ab8ff29b9
Problem 347
===========
The largest integer ≤ 100 that is only divisible by both the primes 2 and
3 is 96, as 96=32*3=2^5*3.For two distinct primes p and q let M(p,q,N) be
the largest positive integer ≤N only divisibleby both p and q and
M(p,q,N)=0 if such a positive integer does not exist.
E.g. M(2,3,100)=96.
M(3,5,100)=75 and not 90 because 90 is divisible by 2 ,3 and 5.
Also M(2,73,100)=0 because there does not exist a positive integer ≤ 100
that is divisible by both 2 and 73.
Answer: 96ce0eabcbe7a2b2eb1197a1bcc5d37b
Problem 348
===========
Many numbers can be expressed as the sum of a square and a cube. Some of
them in more than one way.
2285^2 + 20^3
2223^2 + 66^3
1810^2 + 125^3
1197^2 + 156^3
Answer: f286f9159fc20aeb97a8bf8396ba64de
Problem 349
===========
An ant moves on a regular grid of squares that are coloured either black
or white.
The ant is always oriented in one of the cardinal directions (left, right,
up or down) and moves from square to adjacent square according to the
following rules:
- if it is on a black square, it flips the color of the square to white,
rotates 90 degrees counterclockwise and moves forward one square.
- if it is on a white square, it flips the color of the square to black,
rotates 90 degrees clockwise and moves forward one square.
Starting with a grid that is entirely white, how many squares are black
after 10^18 moves of the ant?
Answer: 412b0faec10b3adb415363d2df26530d
Problem 350
===========
Let f(G, L, N) be the number of lists of size N with gcd ≥ G and lcm ≤ L.
For example:
Answer: cad3ce6a252568bbcb41ca627d7e58ae
Problem 351
===========
Highlighted in green are the points which are hidden from the center by a
point closer to it. It can be seen that for a hexagonal orchard of order
5, 30 points are hidden from the center.
Let H(n) be the number of points hidden from the center in a hexagonal
orchard of order n.
H(5) = 30. H(10) = 138. H(1 000) = 1177848.
p_351_hexorchard.png
Answer: 338481092e945257756075a8d03978fd
Problem 352
===========
Each one of the 25 sheep in a flock must be tested for a rare virus, known
to affect 2% of the sheep population.An accurate and extremely sensitive
PCR test exists for blood samples, producing a clear positive / negative
result, but it is very time-consuming and expensive.
The sheep are split into 5 groups of 5 sheep in each group. For each
group, the 5 samples are mixed together and a single test is performed.
Then,
• If the result is negative, all the sheep in that group are deemed to
be virus-free.
• If the result is positive, 5 additional tests will be performed (a
separate test for each animal) to determine the affected
individual(s).
Since the probability of infection for any specific animal is only 0.02,
the first test (on the pooled samples) for each group will be:
For the current example, it turns out that the most cost-efficient testing
scheme (we'll call it the optimal strategy) requires an average of just
4.155452 tests!
Using the optimal strategy, let T(s,p) represent the average number of
tests needed to screen a flock of s sheep for a virus having probability p
to be present in any individual.
Thus, rounded to six decimal places, T(25, 0.02) = 4.155452 and T(25,
0.10) = 12.702124.
Answer: 2e74b2fb574d6318cdbf2a41ad006de7
Problem 353
===========
A moon could be described by the sphere C(r) with centre (0,0,0) and
radius r.
There are stations on the moon at the points on the surface of C(r) with
integer coordinates. The station at (0,0,r) is called North Pole station,
the station at (0,0,-r) is called South Pole station.
All stations are connected with each other via the shortest road on the
great arc through the stations. A journey between two stations is risky.
If d is the length of the road between two stations, (d/(π r))^2 is a
measure for the risk of the journey (let us call it the risk of the road).
If the journey includes more than two stations, the risk of the journey is
the sum of risks of the used roads.
A direct journey from the North Pole station to the South Pole station has
the length πr and risk 1. The journey from the North Pole station to the
South Pole station via (0,r,0) has the same length, but a smaller risk:
(½πr/(πr))^2+(½πr/(πr))^2=0.5.
The minimal risk of a journey from the North Pole station to the South
Pole station on C(r) is M(r).
Give your answer rounded to 10 digits behind the decimal point in the form
a.bcdefghijk.
Answer: 211b5626459be71baefc78478d18bdc3
Problem 354
===========
p_354_bee_honeycomb.png
Answer: e36240897614dc46e83405ae8cdf198c
Problem 355
===========
Find Co(200000).
Answer: 41cb97b6d02878d79f8b2e3b6c74920a
Problem 356
===========
Let a[n] be the largest real root of a polynomial g(x) = x^3 - 2^n·x^2 +
n.
For example, a[2] = 3.86619826...
p_356_cubicpoly1.gif
p_356_cubicpoly2.gif
Answer: ab2104e80fa7da630ce7fd835d8006ee
Problem 357
===========
Find the sum of all positive integers n not exceeding 100 000 000
such thatfor every divisor d of n, d+n/d is prime.
Answer: ed25b13b18a21c1077fed00ef42f503b
Problem 358
===========
There is only one cyclic number for which, the eleven leftmost digits are
00000000137 and the five rightmost digits are 56789 (i.e., it has the form
00000000137...56789 with an unknown number of digits in the middle). Find
the sum of all its digits.
Answer: 359e1ec8aeaa3932b54f2a5d20fa4f73
Problem 359
===========
Find the sum of all P(f, r) for all positive f and r such that f × r =
71328803586048 and give the last 8 digits as your answer.
Answer: 91525a22396940a99c496efcb75f2eee
Problem 360
===========
Let C(r) be a sphere with radius r and center in the origin O(0,0,0).
Let I(r) be the set of all points with integer coordinates on the surface
of C(r).
Let S(r) be the sum of the Manhattan distances of all elements of I(r) to
the origin O.
E.g. S(45)=34518.
Find S(10^10).
Answer: 82ec91527315eafb7e3acc139eeeb8eb
Problem 361
===========
The Thue-Morse sequence {T[n]} is a binary sequence satisfying:
• T[0] = 0
• T[2n] = T[n]
• T[2n+1] = 1 - T[n]
We define {A[n]} as the sorted sequence of integers such that the binary
expression of each element appears as a subsequence in {T[n]}.
For example, the decimal number 18 is expressed as 10010 in binary. 10010
appears in {T[n]} (T[8] to T[12]), so 18 is an element of {A[n]}.
The decimal number 14 is expressed as 1110 in binary. 1110 never appears
in {T[n]}, so 14 is not an element of {A[n]}.
n 0 1 2 3 4 5 6 7 8 9 10 11 12 …
A[n] 0 1 2 3 4 5 6 9 10 11 12 13 18 …
p_361_Thue-Morse1.gif
Answer: 6540278145900f1fa45b95cc2f9599f1
Problem 362
===========
Let's call Fsf(n) the number of ways n can be factored into one or more
squarefree factors larger than 1, soFsf(54)=2.
S(100)=193.
Answer: b62f0d524bec8653ba7b8a2cab70260b
Problem 363
===========
A cubic Bézier curve is defined by four points: P[0], P[1], P[2] and P[3].
The curve is constructed as follows:
On the segments P[0]P[1], P[1]P[2] and P[2]P[3] the points Q[0],Q[1] and
Q[2] are drawn such that
P[0]Q[0]/P[0]P[1]=P[1]Q[1]/P[1]P[2]=P[2]Q[2]/P[2]P[3]=t (t in [0,1]).
On the segments Q[0]Q[1] and Q[1]Q[2] the points R[0] and R[1] are drawn
such thatQ[0]R[0]/Q[0]Q[1]=Q[1]R[1]/Q[1]Q[2]=t for the same value of t.
On the segment R[0]R[1] the point B is drawn such that R[0]B/R[0]R[1]=t
for the same value of t.The Bézier curve defined by the points P[0], P[1],
P[2], P[3] is the locus of B as Q[0] takes all possible positions on the
segment P[0]P[1]. (Please note that for all points the value of t is the
same.)
[1]Applet
In the applet to the right you can drag the points P[0], P[1], P[2] and
P[3] to see what the Bézier curve (green curve) defined by those points
looks like. You can also drag the point Q[0] along the segment P[0]P[1].
From the construction it is clear that the Bézier curve will be tangent to
the segments P[0]P[1] in P[0] and P[2]P[3] in P[3].
By how many percent does the length of the curve differ from the length of
the quarter circle?
That is, if L is the length of the curve, calculate 100*^(L-π/2)/[(π/2)].
Give your answer rounded to 10 digits behind the decimal point.
Visible links
1. CabriJava.class
Answer: 2bc63386b7cccc64c67f90e719936143
Problem 364
===========
There are N seats in a row. N people come after each other to fill the
seats according to the following rules:
1. If there is any seat whose adjacent seat(s) are not occupied take such
a seat.
2. If there is no such seat and there is any seat for which only one
adjacent seat is occupied take such a seat.
3. Otherwise take one of the remaining available seats.
We can verify that T(10) = 61632 and T(1 000) mod 100 000 007 = 47255094.
Problem 365
===========
Answer: 53addf69042b0cefbeb94f3bd3224918
Problem 366
===========
Two players, Anton and Bernhard, are playing the following game.
There is one pile of n stones.
The first player may remove any positive number of stones, but not the
whole pile.
Thereafter, each player may remove at most twice the number of stones his
opponent took on the previous move.
The player who removes the last stone wins.
E.g. n=5
If the first player takes anything more than one stone the next player
will be able to take all remaining stones.
If the first player takes one stone, leaving four, his opponent will take
also one stone, leaving three stones.
The first player cannot take all three because he may take at most 2x1=2
stones. So let's say he takes also one stone, leaving 2. The second player
can take the two remaining stones and wins.
So 5 is a losing position for the first player.
For some winning positions there is more than one possible move for the
first player.
E.g. when n=17 the first player can remove one or four stones.
Let M(n) be the maximum number of stones the first player can take from a
winning position at his first turn and M(n)=0 for any other position.
Answer: 8a080de12c5163d903b6212dd8086570
Problem 367
===========
Bozo sort, not to be confused with the slightly less efficient bogo sort,
consists out of checking if the input sequence is sorted and if not
swapping randomly two elements. This is repeated until eventually the
sequence is sorted.
Answer: 0589f090524e0eea1544b50eefd0ebd8
Problem 368
===========
If we however omit from this series every term where the denominator has a
9 in it, the series remarkably enough converges to approximately
22.9206766193.
This modified harmonic series is called the Kempner series.
Let us now consider another modified harmonic series by omitting from the
harmonic series every term where the denominator has 3 or more equal
consecutive digits.One can verify that out of the first 1200 terms of the
harmonic series, only 20 terms will be omitted.
These 20 omitted terms are:
1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ,
111 222 333 444 555 666 777 888 999 1000 1110
1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 and 1 .
1111 1112 1113 1114 1115 1116 1117 1118 1119
Problem 369
===========
Let f(n) be the number of ways to choose n cards with a 4 card subset that
is a Badugi. For example, there are 2598960 ways to choose five cards from
a standard 52 card deck, of which 514800 contain a 4 card subset that is a
Badugi, so f(5) = 514800.
Answer: 0f8828f58dbac4f15f296c79b686ed0e
Problem 370
===========
Answer: 85b5048e25677205555a5308991c2e04
Problem 371
===========
E.g. MIC-012 and HAN-988 is a win and RYU-500 and SET-500 too. (as long as
he sees them in the same trip).
Note: We assume that each licence plate seen is equally likely to have any
three digit number on it.
Answer: 537403a97924621c604ce5ab6288b97d
Problem 372
===========
Let R(M, N) be the number of lattice points (x, y) which satisfy M<x≤N,
M<y≤N and is odd.
We can verify that R(0, 100) = 3019 and R(100, 10000) = 29750422.
Find R(2·10^6, 10^9).
p_372_pencilray1.jpg
p_372_pencilray2.gif
Answer: 5fdeda0dca23d12ae3eb1763b2c6f5ea
Problem 373
===========
Every triangle has a circumscribed circle that goes through the three
vertices.Consider all integer sided triangles for which the radius of the
circumscribed circle is integral as well.
Let S(n) be the sum of the radii of the circumscribed circles of all such
triangles for which the radius does not exceed n.
Find S(10^7).
Answer: 888d60a6b2b4b9146d7c9c14ffd82673
Problem 374
===========
Partitions that differ only in the order of their summands are considered
the same.A partition of n into distinct parts is a partition of n in which
every part occurs at most once.
Let f(n) be the maximum product of the parts of any such partition of n
into distinct parts and let m(n) be the number of elements of any such
partition of n with that product.
Answer: 6fcb063062076b5aaaff3e3cd03e4b2f
Problem 375
===========
S[0] =[ ] 290797[ ]
S[n+1] =[ ] S[n]^2 mod 50515093
Let A(i, j) be the minimum of the numbers S[i], S[i+1], ... , S[j] for i ≤
j.
Let M(N) = ΣA(i, j) for 1 ≤ i ≤ j ≤ N.
We can verify that M(10) = 432256955 and M(10 000) = 3264567774119.
Answer: 68a12e3f2e4ccbae9c8555e547fbe096
Problem 376
===========
Die A: 1 4 4 4 4 4
Die B: 2 2 2 5 5 5
Die C: 3 3 3 3 3 6
A game is played by two players picking a die in turn and rolling it. The
player who rolls the highest value wins.
If the first player picks die A and the second player picks die B we get
P(second player wins) = 7/12 > 1/2
If the first player picks die B and the second player picks die C we get
P(second player wins) = 7/12 > 1/2
If the first player picks die C and the second player picks die A we get
P(second player wins) = 25/36 > 1/2
So whatever die the first player picks, the second player can pick another
die and have a larger than 50% chance of winning.
A set of dice having this property is called a nontransitive set of dice.
• There are three six-sided dice with each side having between 1 and N
pips, inclusive.
• Dice with the same set of pips are equal, regardless of which side on
the die the pips are located.
• The same pip value may appear on multiple dice; if both players roll
the same value neither player wins.
• The sets of dice {A,B,C}, {B,C,A} and {C,A,B} are the same set.
Answer: c64df302990eb3738f8ec62ea6b66c0b
Problem 377
===========
There are 16 positive integers that do not have a zero in their digits and
that have a digital sum equal to 5, namely:
5, 14, 23, 32, 41, 113, 122, 131, 212, 221, 311, 1112, 1121, 1211, 2111
and 11111.
Their sum is 17891.
Let f(n) be the sum of all positive integers that do not have a zero in
their digits and have a digital sum equal to n.
Find .
Give the last 9 digits as your answer.
Answer: a915ccbae49de15208c88affba84d206
Problem 378
===========
Let Tr(n) be the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ n
and dT(i) > dT(j) > dT(k).
Tr(20) = 14, Tr(100) = 5772 and Tr(1000) = 11174776.
Problem 379
===========
Let f(n) be the number of couples (x,y) with x and y positive integers, x
≤ y and the least common multiple of x and y equal to n.
Find g(10^12).
Answer: de20f710cb6665c48795072197ad53e0
Problem 380
===========
An m×n maze is an m×n rectangular grid with walls placed between grid
cells such that there is exactly one path from the top-left square to any
other square.
The following are examples of a 9×12 maze and a 15×20 maze:
Let C(m,n) be the number of distinct m×n mazes. Mazes which can be formed
by rotation and reflection from another maze are considered distinct.
Answer: c86d2f4c17c8134fbebed5d37a0f90d7
Problem 381
===========
Problem 382
===========
For example:
The set {3, 4, 5} generates a polygon with sides 3, 4, and 5 (a triangle).
The set {6, 9, 11, 24} generates a polygon with sides 6, 9, 11, and 24 (a
quadrilateral).
The sets {1, 2, 3} and {2, 3, 4, 9} do not generate any polygon at all.
Let U[n] be the set {s[1], s[2], ..., s[n]}. For example, U[10] = {1, 2,
3, 4, 6, 9, 13, 19, 28, 41}.
Let f(n) be the number of subsets of U[n] which generate at least one
polygon.
For example, f(5) = 7, f(10) = 501 and f(25) = 18635853.
Answer: 56a121bcf3bb674d0d3ce561b6b24ea5
Problem 383
===========
Find T[5](10^18).
Answer: c1bc7c945344e1967bfaced9ade895a0
Problem 384
===========
Define the sequence a(n) as the number of adjacent pairs of ones in the
binary expansion of n (possibly overlapping).
E.g.: a(5) = a(101[2]) = 0, a(6) = a(110[2]) = 1, a(7) = a(111[2]) = 2
The sequence s(n) has the remarkable property that all elements are
positive and every positive integer k occurs exactly k times.
Define g(t,c), with 1 ≤ c ≤ t, as the index in s(n) for which t occurs for
the c'th time in s(n).
E.g.: g(3,3) = 6, g(4,2) = 7 and g(54321,12345) = 1220847710.
Define GF(t)=g(F(t),F(t-1)).
Answer: ea0bb1fff1a51b48971762b93aeed103
Problem 385
===========
For any triangle T in the plane, it can be shown that there is a unique
ellipse with largest area that is completely inside T.
For example, if n = 8, there are two such triangles. Their vertices are
(-4,-3),(-4,3),(8,0) and (4,3),(4,-3),(-8,0), and the area of each
triangle is 36. Thus A(8) = 36 + 36 = 72.
It can be verified that A(10) = 252, A(100) = 34632 and A(1000) = 3529008.
Answer: a21c033d9e119c293e51966ea78c9950
Problem 386
===========
Answer: d1d893f7c50910aa10daec5e9352e86d
Problem 387
===========
Also:
201/3=67 which is prime.
Let's call a Harshad number that, when divided by the sum of its digits,
results in a prime a strong Harshad number.
You are given that the sum of the strong, right truncatable Harshad primes
less than 10000 is 90619.
Find the sum of the strong, right truncatable Harshad primes less than
10^14.
Answer: a20cbd8639767decfa2c2c9955eb6be3
Problem 388
===========
From the origin O(0,0,0) all lines are drawn to the other lattice points.
Let D(N) be the number of distinct such lines.
Find D(10^10). Give as your answer the first nine digits followed by the
last nine digits.
Answer: 2bab886c7d98d802d9249c9e12d72c25
Problem 389
===========
Answer: 79a080d38b837547b975c97b44764dfb
Problem 390
===========
Consider the triangle with sides √5, √65 and √68.It can be shown that this
triangle has area 9.
S(n) is the sum of the areas of all triangles with sides √(1+b^2),
√(1+c^2) and √(b^2+c^2) (for positive integers b and c ) that have an
integral area not exceeding n.
S(10^6)=18018206.
Find S(10^10).
Answer: ed7f2fbc05a2fd2033d80de671f35ea3
Problem 391
===========
Let s[k] be the number of 1’s when writing the numbers from 0 to k in
binary.
For example, writing 0 to 5 in binary, we have 0, 1, 10, 11, 100, 101.
There are seven 1’s, so s[5] = 7.
The sequence S = {s[k] : k ≥ 0} starts {0, 1, 2, 4, 5, 7, 9, 12, ...}.
For example:
Let n = 5. c starts at 0.
Player 1 chooses 4, so c becomes 0 + 4 = 4.
Player 2 chooses 5, so c becomes 4 + 5 = 9.
Player 1 chooses 3, so c becomes 9 + 3 = 12.
etc.
Note that c must always belong to S, and each player can increase c by at
most n.
Let M(n) be the highest number the first player can choose at her first
turn to force a win, and M(n) = 0 if there is no such move. For example,
M(2) = 2, M(7) = 1 and M(20) = 4.
Answer: b2947548d4f5c4878c5f788f9849e750
Problem 392
===========
For this problem we would like you to find the postions of the remaining N
inner horizontal and N inner vertical gridlines so that the area occupied
by the red cells is minimized.
The area occupied by the red cells for N = 10 rounded to 10 digits behind
the decimal point is 3.3469640797.
Answer: 3268b0bc489187db3d234c097040d909
Problem 393
===========
An n×n grid of squares contains n^2 ants, one ant per square.
All ants decide to move simultaneously to an adjacent square (usually 4
possibilities, except for ants on the edge of the grid or at the corners).
We define f(n) to be the number of ways this can happen without any ants
ending on the same square and without any two ants crossing the same edge
between two squares.
Answer: 58e4990838fb3d1725872da30f9db748
Problem 394
===========
For x ≥ 1, let E(x) be the expected number of times Jeff repeats the
procedure above with F = ^1/[x].
It can be verified that E(1) = 1, E(2) ≈ 1.2676536759, and E(7.5) ≈
2.1215732071.
Answer: f8ad575e1a03365a60b6429c3b7a64df
Problem 395
===========
Start with a unit square. Then, calling one of the sides its base (in the
animation, the bottom side is the base):
1. Attach a right triangle to the side opposite the base, with the
hypotenuse coinciding with that side and with the sides in a 3-4-5
ratio. Note that the smaller side of the triangle must be on the
'right' side with respect to the base (see animation).
2. Attach a square to each leg of the right triangle, with one of its
sides coinciding with that leg.
3. Repeat this procedure for both squares, considering as their bases the
sides touching the triangle.
It can be shown that there exists at least one rectangle, whose sides are
parallel to the largest square of the Pythagorean tree, which encloses the
Pythagorean tree completely.
Find the smallest area possible for such a bounding rectangle, and give
your answer rounded to 10 decimal places.
p_395_pythagorean.gif
Answer: 505048b0c619161d05b9b3e492f3edc3
Problem 396
===========
For any positive integer n, the nth weak Goodstein sequence {g[1], g[2],
g[3], ...} is defined as:
• g[1] = n
• for k > 1, g[k] is obtained by writing g[k-1] in base k, interpreting
it as a base k + 1 number, and subtracting 1.
For example, the 6th weak Goodstein sequence is {6, 11, 17, 25, ...}:
• g[1] = 6.
• g[2] = 11 since 6 = 110[2], 110[3] = 12, and 12 - 1 = 11.
• g[3] = 17 since 11 = 102[3], 102[4] = 18, and 18 - 1 = 17.
• g[4] = 25 since 17 = 101[4], 101[5] = 26, and 26 - 1 = 25.
and so on.
Let G(n) be the number of nonzero elements in the nth weak Goodstein
sequence.
It can be verified that G(2) = 3, G(4) = 21 and G(6) = 381.
It can also be verified that ΣG(n) = 2517 for 1 ≤ n < 8.
Answer: 4665c73fdca473ccc0643fc982f24e06
Problem 397
===========
On the parabola y = x^2/k, three points A(a, a^2/k), B(b, b^2/k) and C(c,
c^2/k) are chosen.
Answer: 07f769df9543bc05e6318878c34d074d
Problem 398
===========
Inside a rope of length n, n-1 points are placed with distance 1 from each
other and from the endpoints. Among these points, we choose m-1 points at
random and cut the rope at these points to create m segments.
Find E(10^7, 100).Give your answer rounded to 5 decimal places behind the
decimal point.
Answer: fa0a25d62fa225e05fd8736713a9bfc0
Problem 399
===========
The first 15 fibonacci numbers are:
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610.
It can be seen that 8 and 144 are not squarefree: 8 is divisible by 4 and
144 is divisible by 4 and by 9.
So the first 13 squarefree fibonacci numbers are:
1,1,2,3,5,13,21,34,55,89,233,377 and 610.
Note:
For this problem, assume that for every prime p, the first fibonacci
number divisible by p is not divisible by p^2 (this is part of Wall's
conjecture). This has been verified for primes ≤ 3·10^15, but has not been
proven in general.
If it happens that the conjecture is false, then the accepted answer to
this problem isn't guaranteed to be the 100 000 000th squarefree fibonacci
number, rather it represents only a lower bound for that number.
Answer: a0819cfe3be6a04645b8d4fe2345e184
Problem 400
===========
On such a tree two players play a take-away game. On each turn a player
selects a node and removes that node along with the subtree rooted at that
node.
The player who is forced to take the root node of the entire tree loses.
Here are the winning moves of the first player on the first turn for T(k)
from k=1 to k=6.
Let f(k) be the number of winning moves of the first player (i.e. the
moves for which the second player has no winning strategy) on the first
turn of the game when this game is played on T(k).
Problem 401
===========
Let sigma2(n) represent the sum of the squares of the divisors of n.Thus
sigma2(6)=50.
Answer: 982a249d8b45ef10c98c32dabac00751
Problem 402
===========
Answer: fa7ae8e9243f01b0eac10ec5aaff1f42
Problem 403
===========
We also define S(N) as the sum of L(a, b) for all the pairs (a, b) such
that the area of D(a, b) is a rational number and |a|,|b| ≤ N.
We can verify that S(5) = 344 and S(100) = 26709528.
Answer: 31c018e3781a3e170366f01e30f09602
Problem 404
===========
Find C(10^17).
p_404_c_ellipse.gif
Answer: 2d1bc4b93bbc19d9e70c5b04338dea2e
Problem 405
===========
Let f(n) be the number of points where four tiles meet in T(n).
For example, f(1) = 0, f(4) = 82 and f(10^9) mod 17^7 = 126897180.
p_405_tile1.png
p_405_tile2.gif
Answer: 93b712426b768586f88d0bfe597842e6
Problem 406
===========
We are trying to find a hidden number selected from the set of integers
{1, 2, ..., n} by asking questions. Each number (question) we ask, we get
one of three possible answers:
• "Your guess is lower than the hidden number" (and you incur a cost of
a), or
• "Your guess is higher than the hidden number" (and you incur a cost of
b), or
• "Yes, that's it!" (and the game ends).
If we are told that 2 is higher than the hidden number (for a cost of
b=3), then we are sure that "1" is the hidden number (for a total cost of
3).
If we are told that 2 is lower than the hidden number (for a cost of a=2),
then our next question will be "4".
If we are told that 4 is higher than the hidden number (for a cost of
b=3), then we are sure that "3" is the hidden number (for a total cost of
2+3=5).
If we are told that 4 is lower than the hidden number (for a cost of a=2),
then we are sure that "5" is the hidden number (for a total cost of
2+2=4).
Thus, the worst-case cost achieved by this strategy is 5. It can also be
shown that this is the lowest worst-case cost that can be achieved. So, in
fact, we have just described an optimal strategy for the given values of
n, a, and b.
Let F[k] be the Fibonacci numbers: F[k] = F[k-1] + F[k-2] with base cases
F[1] = F[2] = 1.
Find ∑[1≤k≤30] C(10^12, √k, √F[k]), and give your answer rounded to 8
decimal places behind the decimal point.
Answer: 0766b1ee975f5674d30fd6c3c934c6e0
Problem 407
===========
Answer: f4da34a4b357123cb142739a52e010f2
Problem 408
===========
Consider a path from point (x[1], y[1]) to point (x[2], y[2]) using only
unit steps north or east.
Let's call such a path admissible if none of its intermediate points are
inadmissible.
Let P(n) be the number of admissible paths from (0, 0) to (n, n).
It can be verified that P(5) = 252, P(16) = 596994440 and P(1000) mod
1 000 000 007 = 341920854.
Answer: 2c09e247c6144c16cae2358d316affd9
Problem 409
===========
Answer: 56c32e75a2656ec08ce177089bda2f53
Problem 410
===========
Let C be the circle with radius r, x^2 + y^2 = r^2. We choose two points
P(a, b) and Q(-a, c) so that the line passing through P and Q is tangent
to C.
We can verify that F(1, 5) = 10, F(2, 10) = 52 and F(10, 100) = 3384.
Find F(10^8, 10^9) + F(10^9, 10^8).
Answer: 45826f3a23aa321f97acb1d2a8f2170b
Problem 411
===========
We wish to form a path from (0, 0) to (n, n) such that the x and y
coordinates never decrease.
Let S(n) be the maximum number of stations such a path can pass through.
For example, if n = 22, there are 11 distinct stations, and a valid path
can pass through at most 5 stations. Therefore, S(22) = 5.The case is
illustrated below, with an example of an optimal path:
Answer: e351762bf2220ca1396e6a9ee3f6c84f
Problem 412
===========
For integers m, n (0 ≤ n < m), let L(m, n) be an m×m grid with the
top-right n×n grid removed.
Answer: 8919ccca34b7ccc293d33e06872c668d
Problem 413
===========
For example, 5671 is a 4-digit one-child number. Among all its sub-strings
5, 6, 7, 1, 56, 67, 71, 567, 671 and 5671, only 56 is divisible by 4.
Similarly, 104 is a 3-digit one-child number because only 0 is divisible
by 3.
1132451 is a 7-digit one-child number because only 245 is divisible by 7.
Find F(10^19).
Answer: 569ad33af889215704df5a9e278aa004
Problem 414
===========
We can consider the Kaprekar routine for other bases and number of digits.
Unfortunately, it is not guaranteed a Kaprekar constant exists in all
cases; either the routine can end up in a cycle for some input numbers or
the constant the routine arrives at can be different for different input
numbers.
However, it can be shown that for 5 digits and a base b = 6t+3≠9, a
Kaprekar constant exists.
E.g. base 15: (10,4,14,9,5)[15]
base 21: (14,6,20,13,7)[21]
Define C[b] to be the Kaprekar constant in base b for 5 digits.Define the
function sb(i) to be
Note that we can define sb(i) for all integers i < b^5. If i written in
base b takes less than 5 digits, the number is padded with leading zero
digits until we have 5 digits before applying the Kaprekar routine.
Answer: 42f095bdfd71e1ae4ae0ceead1bb1802
Problem 415
===========
An example of a titanic set is S = {(0, 0), (0, 1), (0, 2), (1, 1), (2,
0), (1, 0)}, where the line passing through (0, 1) and (2, 0) does not
pass through any other point in S.
On the other hand, the set {(0, 0), (1, 1), (2, 2), (4, 4)} is not a
titanic set since the line passing through any two points in the set also
passes through the other two.
For any positive integer N, let T(N) be the number of titanic sets S whose
every point (x, y) satisfies 0 ≤ x, y ≤ N.It can be verified that T(1) =
11, T(2) = 494, T(4) = 33554178, T(111) mod 10^8 = 13500401 and
T(10^5) mod 10^8 = 63259062.
Answer: 2357ad217832274f444cae2a6580b193
Problem 416
===========
Answer: 6f398386fdfec57ac166d4970c2bcad2
Problem 417
===========
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can
be seen that 1/7 has a 6-digit recurring cycle.
Unit fractions whose denominator has no other prime factors than 2 and/or
5 are not considered to have a recurring cycle.
We define the length of the recurring cycle of those unit fractions as 0.
Let L(n) denote the length of the recurring cycle of 1/n.You are given
that ∑L(n) for 3 ≤ n ≤ 1 000 000 equals 55535191115.
Answer: 93a7df08c972f1e7788516d056a7e016
Problem 418
===========
• 1 ≤ a ≤ b ≤ c
• a·b·c = n.
Answer: b032468ddb4847d8a2273789379753f5
Problem 419
===========
The look and say sequence goes 1, 11, 21, 1211, 111221, 312211, 13112221,
1113213211, ...
The sequence starts with 1 and all other members are obtained by
describing the previous member in terms of consecutive digits.
It helps to do this out loud:
1 is 'one one' → 11
11 is 'two ones' → 21
21 is 'one two and one one' → 1211
1211 is 'one one, one two and two ones' → 111221
111221 is 'three ones, two twos and one one' → 312211
...
Define A(n), B(n) and C(n) as the number of ones, twos and threes in the
n'th element of the sequence respectively.
One can verify that A(40) = 31254, B(40) = 20259 and C(40) = 11625.
Answer: b27db655498b3d64ad4338fcdc9d178f
Problem 420
===========
We define F(N) as the number of the 2x2 positive integer matrices which
have a trace less than N and which can be expressed as a square of a
positive integer matrix in two different ways.
We can verify that F(50) = 7 and F(1000) = 1019.
Find F(10^7).
p_420_matrix.gif
Answer: e265e34e34fc54e8ceecd5e4b94b1381
Problem 421
===========
Numbers of the form n^15+1 are composite for every integer n > 1.
For positive integers n and m let s(n,m) be defined as the sum of the
distinct prime factors of n^15+1 not exceeding m.
Answer: 481fcc5ff16ccf1645fb136c123ed660
Problem 422
===========
Let H be the hyperbola defined by the equation 12x^2 + 7xy - 12y^2 = 625.
You are given that P[3] = (-19/2, -229/24), P[4] = (1267/144, -37/12) and
P[7] = (17194218091/143327232, 274748766781/1719926784).
Answer: 7034610688a8851f742f912143c1becf
Problem 423
===========
Answer: e2add9d46ebd8ba59a07dca791cd629b
Problem 424
===========
6,X,X,(vCC),(vI),X,X,X,(hH),B,O,(vCA),(vJE),X,(hFE,vD),O,O,O,O,(hA),O,I,
(hJC,vB),O,O,(hJC),H,O,O,O,X,X,X,(hJE),O,O,X
The content of each cell is then described and followed by a comma, going
left to right and starting with the top line.
X = Gray cell, not required to be filled by a digit.
O (upper case letter)= White empty cell to be filled by a digit.
A = Or any one of the upper case letters from A to J to be replaced by its
equivalent digit in the solved puzzle.
( ) = Location of the encrypted sums. Horizontal sums are preceded by a
lower case "h" and vertical sums are preceded by a lower case "v". Those
are followed by one or two upper case letters depending if the sum is a
single digit or double digit one. For double digit sums, the first letter
would be for the "tens" and the second one for the "units". When the cell
must contain information for both a horizontal and a vertical sum, the
first one is always for the horizontal sum and the two are separated by a
comma within the same set of brackets, ex.: (hFE,vD). Each set of brackets
is also immediately followed by a comma.
The required answer to each puzzle is based on the value of each letter
necessary to arrive at the solution and according to the alphabetical
order. As indicated under the example puzzle, its answer would be
8426039571. At least 9 out of the 10 encrypting letters are always part of
the problem description. When only 9 are given, the missing one must be
assigned the remaining digit.
You are given that the sum of the answers for the first 10 puzzles in the
file is 64414157580.
Visible links
1. http://krazydad.com/
2. kakuro200.txt
Answer: c412afe5b5d76dbfbb77443ed5836d89
Problem 425
===========
Two positive numbers A and B are said to be connected (denoted by "A ↔ B")
if one of these conditions holds:
(1) A and B have the same length and differ in exactly one digit; for
example, 123 ↔ 173.
(2) Adding one digit to the left of A (or B) makes B (or A); for example,
23 ↔ 223 and 123 ↔ 23.
For example, 127 is a 2's relative. One of the possible chains is shown
below:
2 ↔ 3 ↔ 13 ↔ 113 ↔ 103 ↔ 107 ↔ 127
However, 11 and 103 are not 2's relatives.
Let F(N) be the sum of the primes ≤ N which are not 2's relatives.
We can verify that F(10^3) = 431 and F(10^4) = 78728.
Find F(10^7).
Answer: 3d229894ba4c585138125e802af2d06e
Problem 426
===========
Consider an infinite row of boxes. Some of the boxes contain a ball. For
example, an initial configuration of 2 consecutive occupied boxes followed
by 2 empty boxes, 2 occupied boxes, 1 empty box, and 2 occupied boxes can
be denoted by the sequence (2, 2, 2, 1, 2), in which the number of
consecutive occupied and empty boxes appear alternately.
• s[0] = 290797
• s[k+1] = s[k]^2 mod 50515093
• t[k] = (s[k] mod 64) + 1
Starting from the initial configuration (t[0], t[1], …, t[10]), the final
state becomes [1, 3, 10, 24, 51, 75].
Starting from the initial configuration (t[0], t[1], …, t[10 000 000]),
find the final state.
Give as your answer the sum of the squares of the elements of the final
state. For example, if the final state is [1, 2, 3] then 14 ( = 1^2 + 2^2
+ 3^2) is your answer.
p_426_baxball1.gif
p_426_baxball2.gif
Answer: b5d8157a351482da47da0512ca374007
Problem 427
===========
For any sequence S, let L(S) be the length of the longest contiguous
subsequence of S with the same value.For example, for the given sequence S
above, L(S) = 3, because of the three consecutive 7's.
Answer: ecb4da2c940b517c63d8d256814dd511
Problem 428
===========
• C[i] has no common interior points with any C[j] for 1 ≤ i, j ≤ k and
i ≠ j,
• C[i] is tangent to both C[in] and C[out] for 1 ≤ i ≤ k,
• C[i] is tangent to C[i+1] for 1 ≤ i < k, and
• C[k] is tangent to C[1].
For example, (5, 5, 5) and (4, 3, 21) are necklace triplets, while it can
be shown that (2, 2, 5) is not.
Let T(n) be the number of necklace triplets (a, b, c) such that a, b and c
are positive integers, and b ≤ n.For example, T(1) = 9, T(20) = 732 and
T(3000) = 438106.
Answer: c6010c109b66b34bf3594e63eb58b446
Problem 429
===========
Let S(n) represent the sum of the squares of the unitary divisors of n.
Thus S(4!)=650.
Answer: ec4f87b0c01680e951326d9e85d2c03f
Problem 430
===========
The following example shows the case N = 8. At the first turn A = 5 and B
= 2, and at the second turn A = 4 and B = 6.
Let E(N, M) be the expected number of disks that show their white side
after M turns.
We can verify that E(3, 1) = 10/9, E(3, 2) = 5/3, E(10, 4) ≈ 5.157 and
E(100, 10) ≈ 51.893.
p_430_flips.gif
Answer: 32b0825d7a110a1a220e80629c413411
Problem 431
===========
Fred the farmer arranges to have a new storage silo installed on his farm
and having an obsession for all things square he is absolutely devastated
when he discovers that it is circular. Quentin, the representative from
the company that installed the silo, explains that they only manufacture
cylindrical silos, but he points out that it is resting on a square base.
Fred is not amused and insists that it is removed from his property.
Quick thinking Quentin explains that when granular materials are delivered
from above a conical slope is formed and the natural angle made with the
horizontal is called the angle of repose. For example if the angle of
repose, $\alpha = 30$ degrees, and grain is delivered at the centre of the
silo then a perfect cone will form towards the top of the cylinder. In the
case of this silo, which has a diameter of 6m, the amount of space wasted
would be approximately 32.648388556 m^3. However, if grain is delivered at
a point on the top which has a horizontal distance of $x$ metres from the
centre then a cone with a strangely curved and sloping base is formed. He
shows Fred a picture.
p_431_grain_silo.png
Answer: 5e5d81aa8bfaf92f68cdef0154c5c238
Problem 432
===========
Find S(510510,10^11).
Give the last 9 digits of your answer.
Answer: e171c2872d650e47589842faa80f5707
Problem 433
===========
Find S(5·10^6).
Answer: 0eeca9fa5cf25a2bfae01f1f04d6cd35
Problem 434
===========
The grid graphs embedded in the Euclidean plane are not rigid, as the
following animation demonstrates:
However, one can make them rigid by adding diagonal edges to the cells.
For example, for the 2x3 grid graph, there are 19 ways to make the graph
rigid:
Note that for the purposes of this problem, we do not consider changing
the orientation of a diagonal edge or adding both diagonal edges to a cell
as a different way of making a grid graph rigid.
Let R(m,n) be the number of ways to make the m × n grid graph rigid.
E.g. R(2,3) = 19 and R(5,5) = 23679901
Answer: f51d9fd41a8ce217682321a020be6fec
Problem 435
===========
For example, F[7](x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7, and
F[7](11) = 268357683.
Answer: 0f08231a97e872f565a085de75743a1c
Problem 436
===========
For example, if the first player draws 0.62 and 0.44, the first player
turn ends since 0.62+0.44 > 1 and x = 0.44.
If the second players draws 0.1, 0.27 and 0.91, the second player turn
ends since 0.62+0.44+0.1+0.27+0.91 > 2 and y = 0.91.Since y > x, the
second player wins.
Louise thinks about it for a second, and objects: "That's not fair".
What is the probability that the second player wins?
Give your answer rounded to 10 places behind the decimal point in the form
0.abcdefghij
Answer: d797ed72189f045e8ea48aa960fec1f3
Problem 437
===========
So the powers of 8 mod 11 are cyclic with period 10, and 8^n + 8^n+1 ≡
8^n+2 (mod 11).
8 is called a Fibonacci primitive root of 11.
Not every prime has a Fibonacci primitive root.
There are 323 primes less than 10000 with one or more Fibonacci primitive
roots and the sum of these primes is 1480491.
Find the sum of the primes less than 100,000,000 with at least one
Fibonacci primitive root.
Answer: 98bb66462d635d8225416a644e4637b0
Problem 438
===========
For an n-tuple of integers t = (a[1], ..., a[n]), let (x[1], ..., x[n]) be
the solutions of the polynomial equation x^n + a[1]x^n-1 + a[2]x^n-2 + ...
+ a[n-1]x + a[n] = 0.
Consider the following two conditions:
Answer: ?
Problem 439
===========
You are given that S(10^3) = 563576517282 and S(10^5) mod 10^9 =
215766508.
Find S(10^11) mod 10^9.
Answer: ?
Problem 440
===========
For example, here are some of the ways to tile a board of length n = 8:
Problem 441
===========
For an integer M, we define R(M) as the sum of 1/(p·q) for all the integer
pairs p and q which satisfy all of these conditions:
• 1 ≤ p < q ≤ M
• p + q ≥ M
• p and q are coprime.
Answer: 152cc265f5461c5055db95a122280416
Problem 442
===========
For example, 2404 and 13431 are eleven-free, while 911 and 4121331 are
not.
Let E(n) be the nth positive eleven-free integer. For example, E(3) = 3,
E(200) = 213 and E(500 000) = 531563.
Find E(10^18).
Answer: c31bb13db787bce9a169dce600aec863
Problem 443
===========
n 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
g(n) 13 14 16 17 18 27 28 29 30 31 32 33 34 51 54 55 60 ...
You are given that g(1 000) = 2524 and g(1 000 000) = 2624152.
Find g(10^15).
Answer: 28f9d9a9bf8fb3d606e0b711b59f42aa
Problem 444
===========
1. The player can scratch his ticket and reveal its worth to everyone at
the table.
2. The player can trade his unscratched ticket for a previous player's
scratched ticket, and then leave the game with that ticket. The previous
player then scratches his newly-acquired ticket and reveals its worth to
everyone at the table.
The game ends once all tickets have been scratched. All players still
remaining at the table must leave with their currently-held tickets.
Assume that each player uses the optimal strategy for maximizing the
expected value of his ticket winnings.
Let E(p) represent the expected number of players left at the table when
the game ends in a game consisting of p players (e.g. E(111) = 5.2912 when
rounded to 5 significant digits).
Answer: e6745c386ba3c0de1bf56897e453c7c8
Problem 445
===========
Find ∑ R(c) for c=C(10 000 000,k), and 1 ≤k≤ 9 999 999.
Give your answer modulo 1 000 000 007.
Answer: ?
Problem 446
===========
Answer: ?
Problem 447
===========
Answer: ?
Problem 448
===========
Problem 449
===========
Phil wants to know how much chocolate is needed to cover one candy centre
with a uniform coat of chocolate one millimeter thick.
Find the amount of chocolate in mm^3 required if a=3 mm and b=1 mm. Give
your answer as the number rounded to 8 decimal places behind the decimal
point.
Answer: 8ac19d0d06980691526883bc8c0950ef
Problem 450
===========
Where R is the radius of the large circle and r the radius of the small
circle.
Let $C(R, r)$ be the set of distinct points with integer coordinates on
the hypocycloid with radius R and r and for which there is a corresponding
value of t such that $\sin(t)$ and $\cos(t)$ are rational numbers.
Let $S(R, r) = \sum_{(x,y) \in C(R, r)} |x| + |y|$ be the sum of the
absolute values of the x and y coordinates of the points in $C(R, r)$.
C(2500, 1000) =
{(2500, 0), (772, 2376), (772, -2376), (516, 1792), (516, -1792), (500,
0), (68, 504), (68, -504),
(-1356, 1088), (-1356, -1088), (-1500, 1000), (-1500, -1000)}
Find T(10^6).
Answer: ?
Problem 451
===========
Let I(n) be the largest positive number m smaller than n-1 such that the
modular inverse of m modulo n equals m itself.
So I(15)=11.
Also I(100)=51 and I(7)=1.
Answer: 9848878734a1d751a0e428147ab0b4aa
Problem 452
===========
Define F(m,n) as the number of n-tuples of positive integers for which the
product of the elements doesn't exceed m.
Problem 453
===========
It can also be verified that Q(3, 7) = 39590, Q(12, 3) = 309000 and Q(123,
45) = 70542215894646.
Answer: ?
Problem 454
===========
1 1 1
─ + ─ = ─
x y n
For a limit L we define F(L) as the number of solutions which satisfy x <
y ≤ L.
Answer: cf4e45f50c511e558b3dccb3ed481cb5
Problem 455
===========
Let f(n) be the largest positive integer x less than 10^9 such that the
last 9 digits of n^x form the number x (including leading zeros), or zero
if no such integer exists.
For example:
Answer: 22d6cf30a29e14e5c78dca980edc2796
Problem 456
===========
Define:
x[n] = (1248^n mod 32323) - 16161
y[n] = (8421^n mod 30103) - 15051
P[n] = {(x[1], y[1]), (x[2], y[2]), ..., (x[n], y[n])}
Let C(n) be the number of triangles whose vertices are in P[n] which
contain the origin in the interior.
Examples:
C(8) = 20
C(600) = 8950634
C(40 000) = 2666610948988
Answer: e2811a92b4658ca420be740f6c66572b
Problem 457
===========
Find SR(10^7).
Answer: 5eae79c2f4887f6cf08c099840317a51
Problem 458
===========
Consider the alphabet A made out of the letters of the word "project":
A={c,e,j,o,p,r,t}.
Let T(n) be the number of strings of length n consisting of letters from A
that do not have a substring that is one of the 5040 permutations of
"project".
T(7)=7^7-7!=818503.
Answer: ?
Problem 459
===========
Players alternate turns. A player wins by turning the grid all black.
Let W(N) be the number of winning moves for the first player on a N by N
board with all disks white, assuming perfect play.
W(1) = 1, W(2) = 0, W(5) = 8 and W(10^2) = 31395.
For N=5, the first player's eight winning first moves are:
Find W(10^6).
Answer: ?
Problem 460
===========
On the Euclidean plane, an ant travels from point A(0, 1) to point B(d, 1)
for an integer d.
In each step, the ant at point (x[0], y[0]) chooses one of the lattice
points (x[1], y[1]) which satisfy x[1] ≥ 0 and y[1] ≥ 1 and goes straight
to (x[1], y[1]) at a constant velocity v. The value of v depends on y[0]
and y[1] as follows:
The left image is one of the possible paths for d = 4. First the ant goes
from A(0, 1) to P[1](1, 3) at velocity (3 - 1) / (ln(3) - ln(1)) ≈ 1.8205.
Then the required time is sqrt(5) / 1.8205 ≈ 1.2283.
From P[1](1, 3) to P[2](3, 3) the ant travels at velocity 3 so the
required time is 2 / 3 ≈ 0.6667. From P[2](3, 3) to B(4, 1) the ant
travels at velocity (1 - 3) / (ln(1) - ln(3)) ≈ 1.8205 so the required
time is sqrt(5) / 1.8205 ≈ 1.2283.
Thus the total required time is 1.2283 + 0.6667 + 1.2283 = 3.1233.
The right image is another path. The total required time is calculated as
0.98026 + 1 + 0.98026 = 2.96052. It can be shown that this is the quickest
path for d = 4.
Let F(d) be the total required time if the ant chooses the quickest path.
For example, F(4) ≈ 2.960516287.
We can verify that F(10) ≈ 4.668187834 and F(100) ≈ 9.217221972.
Answer: 134fd9e25365ddb970971dd21f386408
Problem 461
===========
Let g(n) = a^2 + b^2 + c^2 + d^ 2 for a, b, c, d that minimize the error:
| f[n](a) + f[n](b) + f[n](c) + f[n](d) - π|
(where |x| denotes the absolute value of x).
Find g(10000). ^
Answer: 70c3eff774c9d5cdb29284c16b9d1bc6
Problem 462
===========
Answer: ?
Problem 463
===========
• $f(1)=1$
• $f(3)=3$
• $f(2n)=f(n)$
• $f(4n + 1)=2f(2n + 1) - f(n)$
• $f(4n + 3)=3f(2n + 1) - 2f(n)$
Answer: 95481696a65b0c1d9f73186a693686f5
Problem 464
===========
Let P(a,b) be the number of integers n in the interval [a,b] such that
μ(n) = 1.
Let N(a,b) be the number of integers n in the interval [a,b] such that
μ(n) = -1.
For example, P(2,10) = 2 and N(2,10) = 4.
• 1 ≤ a ≤ b ≤ n,
• 99·N(a,b) ≤ 100·P(a,b), and
• 99·P(a,b) ≤ 100·N(a,b).
For example, C(10) = 13, C(500) = 16676 and C(10 000) = 20155319.
Problem 465
===========
The kernel of a polygon is defined by the set of points from which the
entire polygon's boundary is visible. We define a polar polygon as a
polygon for which the origin is strictly contained inside its kernel.
For example, only the first of the following is a polar polygon (the
kernels of the second, third, and fourth do not strictly contain the
origin, and the fifth does not have a kernel at all):
Notice that the first polygon has three consecutive collinear vertices.
Let P(n) be the number of polar polygons such that the vertices (x, y)
have integer coordinates whose absolute values are not greater than n.
For example, P(1) = 131, P(2) = 1648531, P(3) = 1099461296175 and P(343)
mod 1 000 000 007 = 937293740.
Answer: ?
Problem 466
===========
× 1 2 3 4
1 1 2 3 4
2 2 4 6 8
3 3 6 9 12
Answer: ?
Problem 467
===========
Let p(n) be the nth prime number, and let c(n) be the nth composite
number. For example, p(1) = 2, p(10) = 29, c(1) = 4 and c(10) = 18.
{p(i) : i ≥ 1} = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...}
{c(i) : i ≥ 1} = {4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}
Let P^D the sequence of the digital roots of {p(i)} (C^D is defined
similarly for {c(i)}):
P^D = {2, 3, 5, 7, 2, 4, 8, 1, 5, 2, ...}
C^D = {4, 6, 8, 9, 1, 3, 5, 6, 7, 9, ...}
Answer: ?
Problem 468
===========
Answer: ?
Problem 469
===========
When there aren't any suitable chairs left, the fraction C of empty chairs
is determined.
We also define E(N) as the expected value of C.
We can verify that E(4) = 1/2 and E(6) = 5/9.
Find E(10^18). Give your answer rounded to fourteen decimal places in the
form 0.abcdefghijklmn.
Answer: 3c2b641262880db5b735cfa4d4c957bc
Problem 470
===========
Let t represent the maximum number of turns the game lasts. If t = 0, then
the game ends immediately. Otherwise, on each turn i, the player rolls a
die. After rolling, if i < t the player can either stop the game and
receive a prize equal to the value of the current roll, or discard the
roll and try again next turn. If i = t, then the roll cannot be discarded
and the prize must be accepted. Before the game begins, t is chosen by the
player, who must then pay an up-front cost ct for some constant c. For c =
0, t can be chosen to be infinite (with an up-front cost of 0). Let R(d,
c) be the expected profit (i.e. net gain) that the player receives from a
single game of optimally-played Ramvok, given a fair d-sided die and cost
constant c. For example, R(4, 0.2) = 2.65. Assume that the player has
sufficient funds for paying any/all up-front costs.
Let S(d, c) be the expected profit that the player receives from an
optimally-played game of Super Ramvok, given a fair d-sided die to start
(with all sides visible), and cost constant c. For example, S(6, 1) =
208.3.
Answer: ?
Problem 471
===========
Let r(a,b) be the radius of the incircle of ΔABC when the incircle has
center (2b, 0) and A has coordinates $\left( \frac a 2, \frac {\sqrt 3} 2
b\right)$.
Find G(10^11).
Answer: ?
Problem 472
===========
There are N seats in a row. N people come one after another to fill the
seats according to the following rules:
Note that due to rule 1, some seats will surely be left unoccupied, and
the maximum number of people that can be seated is less than N (for N >
1).
We see that if the first person chooses correctly, the 15 seats can seat
up to 7 people.
We can also see that the first person has 9 choices to maximize the number
of people that may be seated.
Let f(N) be the number of choices the first person has to maximize the
number of occupants for N seats in a row. Thus, f(1) = 1, f(15) = 9,
f(20) = 6, and f(500) = 16.
Find ∑f(N) for 1 ≤ N ≤ 10^12. Give the last 8 digits of your answer.
Answer: ?
Problem 473
===========
The sum of the positive integers not exceeding 1000 whose phigital
representation is palindromic is 4345.
Find the sum of the positive integers not exceeding $10^{10}$ whose
phigital representation is palindromic.
Answer: a4ea7a2040b6385b6d12863fd693e434
Problem 474
===========
For a positive integer n and digits d, we define F(n, d) as the number of
the divisors of n whose last digits equal d.
For example, F(84, 4) = 3. Among the divisors of 84 (1, 2, 3, 4, 6, 7, 12,
14, 21, 28, 42, 84), three of them (4, 14, 84) have the last digit 4.
We can also verify that F(12!, 12) = 11 and F(50!, 123) = 17888.
Answer: ?
Problem 475
===========
12n musicians participate at a music festival. On the first day, they form
3n quartets and practice all day.
It is a disaster. At the end of the day, all musicians decide they will
never again agree to play with any member of their quartet.
On the second day, they form 4n trios, each musician avoiding his previous
quartet partners.
Let f(12n) be the number of ways to organize the trios amongst the 12n
musicians.
You are given f(12) = 576 and f(24) mod 1 000 000 007 = 509089824.
Answer: 6be2411783d9ca8e7ad174b269a85be5
Problem 476
===========
Let S(n) be the average value of R(a, b, c) over all integer triplets (a,
b, c) such that 1 ≤ a ≤ b ≤ c < a + b ≤ n
Answer: 4d6a99b2a0f22af561aeeb69c0126fef