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. For example (with q = 100000007) : f(2) = 229, f(4) = 117805, f(10) mod q = 96149360, f(10^3) mod q = 24806056, f(10^6) mod q = 30808124. Find f(10^10000) mod 100000007. 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. E.g., let the ordered pair(6,14) describe a configuration with 6 stones in the smaller pile and 14 stones in the larger pile, then the first player can remove 6 or 12 stones from the larger 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. Define S(N) as the sum of (x[i]+y[i]) for all losing configurations (x[i],y[i]), 0 < x[i] < y[i] ≤ N. We can verify that S(10) = 211 and S(10^4) = 230312207313. Find S(10^16) mod 7^10. Answer: 5b1ce9ac67e0ad6690c728ccba6f0070 Problem 326 =========== Let a[n] be a sequence recursively defined by: . So the first 10 elements of a[n] are: 1,1,0,3,0,3,5,4,1,9. Let f(N,M) represent the number of pairs (p,q) such that: It can be seen that f(10,10)=4 with the pairs (3,3), (5,5), (7,9) and (9,10). You are also given that f(10^4,10^3)=97158. Find f(10^12,10^6). p_326_formula1.gif p_326_formula2.gif Answer: d95dff1a5ceee0064993d98defdd603e Problem 327 =========== A series of three rooms are connected to each other by automatic doors. 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. It is possible to travel through six rooms using a total of 123 security cards while carrying a maximum of 3 cards. 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. For example, M(3,6)=123 and M(4,6)=23. And, ΣM(C,6)=146 for 3 ≤ C ≤ 4. You are given that ΣM(C,10)=10382 for 3 ≤ C ≤ 10. Find ΣM(C,30) for 3 ≤ C ≤ 40. 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: • "Your guess is lower than the hidden number", or • "Yes, that's it!", or • "Your guess is higher than the hidden number". 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). If n=8, we might decide to use a "binary search" type of strategy: Our first question would be "4" and if the hidden number is higher than 4 we will need one or two additional questions. Let our second question be "6". If the hidden number is still higher than 6, we will need a third question in order to discriminate between 7 and 8. Thus, our third question will be "7" and the total cost for this worst-case scenario will be 4+6+7=17. 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. Let C(n) be the worst-case cost achieved by an optimal strategy for n, as described above. Thus C(1) = 0, C(2) = 1, C(3) = 2 and C(8) = 12. Similarly, C(100) = 400 and C(n) = 17575. Find C(n). p_328_sum1.gif p_328_sum2.gif Answer: 92a3220ad5b17a562c039e6e93d6df90 Problem 329 =========== Susan has a prime frog. Her frog is jumping around over 500 squares numbered 1 to 500.He can only jump one square to the left or to the right, with equal probability, and he cannot jump outside the range [1;500]. (if it lands at either end, it automatically jumps to the only available square on the next move.) When he is on a square with a prime number on it, he croaks 'P' (PRIME) with probability 2/3 or 'N' (NOT PRIME) with probability 1/3 just before jumping to the next square. When he is on a square with a number on it that is not a prime he croaks 'P' with probability 1/3 or 'N' with probability 2/3 just before jumping to the next square. 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? Give your answer as a fraction p/q in reduced form. Answer: e392a8b1b053c83e68663e08456bb392 Problem 330 =========== An infinite sequence of real numbers a(n) is defined for all integers n as follows: 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 with e = 2.7182818... being Euler's constant. It can be shown that a(n) is of A(n) e + B(n) for integers A(n) and B(n). the form n! For example a(10) = 328161643 e − 652694486 . 10! 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. It can be proven that 3 is the minimal number of turns to finish this game. 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 C[N] be the following configuration of a board with N×N disks: A disk at (x,y) satisfying , shows its black side; otherwise, it shows its white side. C[5] is shown above. 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 =========== A spherical triangle is a figure formed on the surface of a sphere by three great circular arcs intersecting pairwise in three vertices. 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). For example A(14) is 3.294040 rounded to six decimal places. Find A(r). Give your answer rounded to six decimal places. 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 define P(n) as the number of valid partitions of n. For example, P(11) = 2. 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. Find the sum of the primes q <1000000 such that P(q)=1. Answer: 8408ff3a470a94dbfca1819249eb547d Problem 334 =========== In Plato's heaven, there exist an infinite number of bowls in a straight line. Each bowl either contains some or none of a finite number of beans. A child plays a game, which allows only one kind of move: removing two beans from any bowl, and putting one in each of the two adjacent bowls. The game ends when each bowl contains either one or no beans. For example, consider two adjacent bowls containing 2 and 3 beans respectively, all other bowls being empty. The following eight moves will finish the game: You are given the following sequences: t[0] = 123456. t[i-1] , if t[i-1] is even t[i] = 2 t[i-1] 926252, if t[i-1] is odd 2 where ⌊x⌋ is the floor function and is the bitwise XOR operator. b[i] = ( t[i] mod 2^11) + 1. 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: So with 5 bowls it takes Peter 15 moves to return to the initial situation. 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. Find M(2^k+1). Give your answer modulo 7^9. p_335_mancala.gif p_335_sum.gif Answer: 9a519cfa0ebdd4d1dd318f14b5799eea Problem 336 =========== A train is used to transport four carriages in the order: ABCD. However, sometimes when the train arrives to collect the carriages they are not in the correct order. To rearrange the carriages they are all shunted on to a large rotating turntable. After the carriages are uncoupled at a specific point the train moves off the turntable pulling the carriages still attached with it. The remaining carriages are rotated 180 degrees. All of the carriages are then rejoined and this process is repeated as often as necessary in order to obtain the least number of uses of the turntable. Some arrangements, such as ADCB, can be solved easily: the carriages are separated between A and D, and after DCB are rotated the correct order has been achieved. 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. It can be verified that there are 24 maximix arrangements for six carriages, of which the tenth lexicographic maximix arrangement is DFAECB. Find the 2011^th lexicographic maximix arrangement for eleven carriages. p_336_maximix.gif Answer: 7968e48fc692ce25bf7f5494f4ab6814 Problem 337 =========== Let {a[1], a[2],..., a[n]} be an integer sequence of length n such that: • a[1] = 6 • for all 1 ≤ i < n : φ(a[i]) < φ(a[i+1]) < a[i] < a[i+1] ^1 Let S(N) be the number of such sequences with a[n] ≤ N. For example, S(10) = 4: {6}, {6, 8}, {6, 8, 9} and {6, 10}. We can verify that S(100) = 482073668 and S(10 000) mod 10^8 = 73808307. Find S(20 000 000) mod 10^8. ^1 φ denotes Euler's totient function. Answer: a60bbbe1b90254043fb92820492a2f96 Problem 338 =========== A rectangular sheet of grid paper with integer dimensions w × h is given. Its grid spacing is 1. When we cut the sheet along the grid lines into two pieces and rearrange those pieces without overlap, we can make new rectangles with different dimensions. For example, from a sheet with dimensions 9 × 4 , we can make rectangles with dimensions 18 × 2, 12 × 3 and 6 × 6 by cutting and rearranging as below: Similarly, from a sheet with dimensions 9 × 8 , we can make rectangles with dimensions 18 × 4 and 12 × 6 . 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. Find G(10^12). Give your answer modulo 10^8. 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 Initially each flock consists of n sheep. Each sheep (regardless of colour) is equally likely to be the next sheep to bleat. After a sheep has bleated and a sheep from the other flock has crossed over, Peredur may remove a number of white sheep in order to maximize the expected final number of black sheep. Let E(n) be the expected final number of black sheep if Peredur uses an optimal strategy. 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 fixed integers a, b, c, define the crazy function F(n) as follows: F(n) = n - c for all n > b F(n) = F(a + F(a + F(a + F(a + n)))) for all n ≤ b. Also, define S(a, b, c) = . For example, if a = 50, b = 2000 and c = 40, then F(0) = 3240 and F(2000) = 2040. Also, S(50, 2000, 40) = 5204240. Find the last 9 digits of S(21^7, 7^21, 12^7). p_340_formula.gif Answer: fc838afe9ecde39bbe230923d7b50775 Problem 341 =========== The Golomb's self-describing sequence {G(n)} is the only nondecreasing sequence of natural numbers such that n appears exactly G(n) times in the sequence. The values of G(n) for the first few n are 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 … You are given that G(10^3) = 86, G(10^6) = 6137. You are also given that ΣG(n^3) = 153506976 for 1 ≤ n < 10^3. Find ΣG(n^3) for 1 ≤ n < 10^6. Answer: 7c163c3b4886943667b5c89db0a6cd02 Problem 342 =========== Consider the number 50. 50^2 = 2500 = 2^2 × 5^4, so φ(2500) = 2 × 4 × 5^3 = 8 × 5^3 = 2^3 × 5^3. ^1 So 2500 is a square and φ(2500) is a cube. Find the sum of all numbers n, 1 < n < 10^10 such that φ(n^2) is a cube. ^1 φ denotes Euler's totient function. Answer: 0e9add0383d4116c7c5cb3dc73fc0536 Problem 343 =========== For any positive integer k, a finite sequence a[i] of fractions x[i]/y[i] is defined by: a[1] = 1/k and a[i] = (x[i-1]+1)/(y[i-1]-1) reduced to lowest terms for i>1. When a[i] reaches some integer n, the sequence stops. (That is, when y[i]=1.) Define f(k) = n. For example, for k = 20: 1/20 → 2/19 → 3/18 = 1/6 → 2/5 → 3/4 → 4/3 → 5/2 → 6/1 = 6 So f(20) = 6. Also f(1) = 1, f(2) = 2, f(3) = 1 and Σf(k^3) = 118937 for 1 ≤ k ≤ 100. Find Σf(k^3) for 1 ≤ k ≤ 2×10^6. Answer: 0e10bd111425ad8e1343ac79dac7bb0e Problem 344 =========== One variant of N.G. de Bruijn's silver dollar game can be described as follows: 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. The winner is the player who pockets the silver dollar. A winning configuration is an arrangement of coins on the strip where the first player can force a win no matter what the second player does. Let W(n,c) be the number of winning configurations for a strip of n squares, c worthless coins and one silver dollar. You are given that W(10,2) = 324 and W(100,10) = 1514704946113500. 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 Find the Matrix Sum of: 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 =========== The number 7 is special, because 7 is 111 written in base 2, and 11 written in base 6 (i.e. 7[10] = 11[6] = 111[2]). In other words, 7 is a repunit in at least two bases b > 1. We shall call a positive integer with this property a strong repunit. It can be verified that there are 8 strong repunits below 50: {1,7,13,15,21,31,40,43}. Furthermore, the sum of all strong repunits below 1000 equals 15864. Find the sum of all strong repunits below 10^12. 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. Let S(N) be the sum of all distinct M(p,q,N).S(100)=2262. Find S(10 000 000). 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. Consider the palindromic numbers that can be expressed as the sum of a square and a cube, both greater than 1, in exactly 4 different ways. For example, 5229225 is a palindromic number and it can be expressed in exactly 4 different ways: 2285^2 + 20^3 2223^2 + 66^3 1810^2 + 125^3 1197^2 + 156^3 Find the sum of the five smallest such palindromic numbers. 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 =========== A list of size n is a sequence of n natural numbers. Examples are (2,4,6), (2,6,4), (10,6,15,6), and (11). The greatest common divisor, or gcd, of a list is the largest natural number that divides all entries of the list. Examples: gcd(2,6,4) = 2, gcd(10,6,15,6) = 1 and gcd(11) = 11. The least common multiple, or lcm, of a list is the smallest natural number divisible by each entry of the list. Examples: lcm(2,6,4) = 12, lcm(10,6,15,6) = 30 and lcm(11) = 11. Let f(G, L, N) be the number of lists of size N with gcd ≥ G and lcm ≤ L. For example: f(10, 100, 1) = 91. f(10, 100, 2) = 327. f(10, 100, 3) = 1135. f(10, 100, 1000) mod 101^4 = 3286053. Find f(10^6, 10^12, 10^18) mod 101^4. Answer: cad3ce6a252568bbcb41ca627d7e58ae Problem 351 =========== A hexagonal orchard of order n is a triangular lattice made up of points within a regular hexagon with side n. The following is an example of a hexagonal orchard of order 5: 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. Find H(100 000 000). 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. Because of the high cost, the vet-in-charge suggests that instead of performing 25 separate tests, the following procedure can be used instead: 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: • Negative (and no more tests needed) with probability 0.98^5 = 0.9039207968. • Positive (5 additional tests needed) with probability 1 - 0.9039207968 = 0.0960792032. Thus, the expected number of tests for each group is 1 + 0.0960792032 × 5 = 1.480396016. Consequently, all 5 groups can be screened using an average of only 1.480396016 × 5 = 7.40198008 tests, which represents a huge saving of more than 70% ! Although the scheme we have just described seems to be very efficient, it can still be improved considerably (always assuming that the test is sufficiently sensitive and that there are no adverse effects caused by mixing different samples). E.g.: • We may start by running a test on a mixture of all the 25 samples. It can be verified that in about 60.35% of the cases this test will be negative, thus no more tests will be needed. Further testing will only be required for the remaining 39.65% of the cases. • If we know that at least one animal in a group of 5 is infected and the first 4 individual tests come out negative, there is no need to run a test on the fifth animal (we know that it must be infected). • We can try a different number of groups / different number of animals in each group, adjusting those numbers at each level so that the total expected number of tests will be minimised. To simplify the very wide range of possibilities, there is one restriction we place when devising the most cost-efficient testing scheme: whenever we start with a mixed sample, all the sheep contributing to that sample must be fully screened (i.e. a verdict of infected / virus-free must be reached for all of them) before we start examining any other animals. 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. Find ΣT(10000, p) for p=0.01, 0.02, 0.03, ... 0.50. Give your answer rounded to six decimal places. 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). You are given that M(7)=0.1784943998 rounded to 10 digits behind the decimal point. Find ∑M(2^n-1) for 1≤n≤15. Give your answer rounded to 10 digits behind the decimal point in the form a.bcdefghijk. Answer: 211b5626459be71baefc78478d18bdc3 Problem 354 =========== Consider a honey bee's honeycomb where each cell is a perfect regular hexagon with side length 1. One particular cell is occupied by the queen bee. For a positive real number L, let B(L) count the cells with distance L from the queen bee cell (all distances are measured from centre to centre); you may assume that the honeycomb is large enough to accommodate for any distance we wish to consider. For example, B(√3) = 6, B(√21) = 12 and B(111 111 111) = 54. Find the number of L ≤ 5·10^11 such that B(L) = 450. p_354_bee_honeycomb.png Answer: e36240897614dc46e83405ae8cdf198c Problem 355 =========== Define Co(n) to be the maximal possible sum of a set of mutually co-prime elements from {1, 2, ..., n}. For example Co(10) is 30 and hits that maximum on the subset {1, 5, 7, 8, 9}. You are given that Co(30) = 193 and Co(100) = 1356. 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... Find the last eight digits of. Note: represents the floor function. p_356_cubicpoly1.gif p_356_cubicpoly2.gif Answer: ab2104e80fa7da630ce7fd835d8006ee Problem 357 =========== Consider the divisors of 30: 1,2,3,5,6,10,15,30. It can be seen that for every divisor d of 30, d+30/d is prime. 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 =========== A cyclic number with n digits has a very interesting property: When it is multiplied by 1, 2, 3, 4, ... n, all the products have exactly the same digits, in the same order, but rotated in a circular fashion! The smallest cyclic number is the 6-digit number 142857 : 142857 × 1 = 142857 142857 × 2 = 285714 142857 × 3 = 428571 142857 × 4 = 571428 142857 × 5 = 714285 142857 × 6 = 857142 The next cyclic number is 0588235294117647 with 16 digits : 0588235294117647 × 1 = 0588235294117647 0588235294117647 × 2 = 1176470588235294 0588235294117647 × 3 = 1764705882352941 ... 0588235294117647 × 16 = 9411764705882352 Note that for cyclic numbers, leading zeros are important. 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 =========== An infinite number of people (numbered 1, 2, 3, etc.) are lined up to get a room at Hilbert's newest infinite hotel. The hotel contains an infinite number of floors (numbered 1, 2, 3, etc.), and each floor contains an infinite number of rooms (numbered 1, 2, 3, etc.). Initially the hotel is empty. Hilbert declares a rule on how the n^th person is assigned a room: person n gets the first vacant room in the lowest numbered floor satisfying either of the following: • the floor is empty • the floor is not empty, and if the latest person taking a room in that floor is person m, then m + n is a perfect square Person 1 gets room 1 in floor 1 since floor 1 is empty. Person 2 does not get room 2 in floor 1 since 1 + 2 = 3 is not a perfect square. Person 2 instead gets room 1 in floor 2 since floor 2 is empty. Person 3 gets room 2 in floor 1 since 1 + 3 = 4 is a perfect square. Eventually, every person in the line gets a room in the hotel. Define P(f, r) to be n if person n occupies room r in floor f, and 0 if no person occupies the room. Here are a few examples: P(1, 1) = 1 P(1, 2) = 3 P(2, 1) = 2 P(10, 20) = 440 P(25, 75) = 4863 P(99, 100) = 19454 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 =========== Given two points (x[1],y[1],z[1]) and (x[2],y[2],z[2]) in three dimensional space, the Manhattan distance between those points is defined as |x[1]-x[2]|+|y[1]-y[2]|+|z[1]-z[2]|. 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] The first several terms of {T[n]} are given as follows: 01101001100101101001011001101001.... 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]}. The first several terms of A[n] are given as follows: 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 … We can also verify that A[100] = 3251 and A[1000] = 80852364498. Find the last 9 digits of . p_361_Thue-Morse1.gif Answer: 6540278145900f1fa45b95cc2f9599f1 Problem 362 =========== Consider the number 54. 54 can be factored in 7 distinct ways into one or more factors larger than 1: 54, 2×27, 3×18, 6×9, 3×3×6, 2×3×9 and 2×3×3×3. If we require that the factors are all squarefree only two ways remain: 3×3×6 and 2×3×3×3. 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. Let S(n) be ∑Fsf(k) for k=2 to n. S(100)=193. Find S(10 000 000 000). 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]. A cubic Bézier curve with P[0]=(1,0), P[1]=(1,v), P[2]=(v,1) and P[3]=(0,1) is used to approximate a quarter circle. The value v>0 is chosen such that the area enclosed by the lines OP[0], OP[3] and the curve is equal to ^π/[4] (the area of the quarter circle). 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. Let T(N) be the number of possibilities that N seats are occupied by N people with the given rules. The following figure shows T(4)=8. We can verify that T(10) = 61632 and T(1 000) mod 100 000 007 = 47255094. Find T(1 000 000) mod 100 000 007. p_364_comf_dist.gif Answer: d631977573d415a4766de9e6bd388cca Problem 365 =========== The binomial coeffient C(10^18,10^9) is a number with more than 9 billion (9×10^9) digits. Let M(n,k,m) denote the binomial coefficient C(n,k) modulo m. Calculate ∑M(10^18,10^9,p*q*r) for 10001/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. We wish to investigate how many sets of nontransitive dice exist. We will assume the following conditions: • 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. For N = 7 we find there are 9780 such sets. How many are there for N = 30 ? 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 T(n) be the n^th triangle number, so T(n) = n (n+1) . 2 Let dT(n) be the number of divisors of T(n). E.g.:T(7) = 28 and dT(7) = 6. 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. Find Tr(60 000 000). Give the last 18 digits of your answer. Answer: 336745dc9d90928596237c4b471a8927 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. Let g be the summatory function of f, i.e.: g(n) = ∑ f(i) for 1 ≤ i ≤ n. You are given that g(10^6) = 37429395. 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. It can be verified that C(1,1) = 1, C(2,2) = 4, C(3,4) = 2415, and C(9,12) = 2.5720e46 (in scientific notation rounded to 5 significant digits). Find C(100,500) and write your answer in scientific notation rounded to 5 significant digits. When giving your answer, use a lowercase e to separate mantissa and exponent.E.g. if the answer is 1234567891011 then the answer format would be 1.2346e12. Answer: c86d2f4c17c8134fbebed5d37a0f90d7 Problem 381 =========== For a prime p let S(p) = (∑(p-k)!) mod(p) for 1 ≤ k ≤ 5. For example, if p=7, (7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)! = 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2 = 872. As 872 mod(7) = 4, S(7) = 4. It can be verified that ∑S(p) = 480 for 5 ≤ p < 100. Find ∑S(p) for 5 ≤ p < 10^8. Answer: 80c84973a9643e46d49d79d7284e7ff3 Problem 382 =========== A polygon is a flat shape consisting of straight line segments that are joined to form a closed chain or circuit. A polygon consists of at least three sides and does not self-intersect. A set S of positive numbers is said to generate a polygon P if: • no two sides of P are the same length, • the length of every side of P is in S, and • S contains no other value. 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. Consider the sequence s, defined as follows: • s[1] = 1, s[2] = 2, s[3] = 3 • s[n] = s[n-1] + s[n-3] for n > 3. 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. Find the last 9 digits of f(10^18). Answer: 56a121bcf3bb674d0d3ce561b6b24ea5 Problem 383 =========== Let f[5](n) be the largest integer x for which 5^x divides n. For example, f[5](625000) = 7. Let T[5](n) be the number of integers i which satisfy f[5]((2·i-1)!) < 2·f[5](i!) and 1 ≤ i ≤ n. It can be verified that T[5](10^3) = 68 and T[5](10^9) = 2408210. 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 Define the sequence b(n) = (-1)^a(n). This sequence is called the Rudin-Shapiro sequence. Also consider the summatory sequence of b(n): . The first couple of values of these sequences are: n 0 1 2 3 4 5 6 7 a(n) 0 0 0 1 0 0 1 2 b(n) 1 1 1 -1 1 1 -1 1 s(n) 1 2 3 2 3 4 3 4 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. Let F(n) be the fibonacci sequence defined by: F(0)=F(1)=1 and F(n)=F(n-1)+F(n-2) for n>1. Define GF(t)=g(F(t),F(t-1)). Find ΣGF(t) for 2≤t≤45. 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 a given n, consider triangles T such that: - the vertices of T have integer coordinates with absolute value ≤ n, and - the foci^1 of the largest-area ellipse inside T are (√13,0) and (-√13,0). Let A(n) be the sum of the areas of all such triangles. 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. Find A(1 000 000 000). ^1The foci (plural of focus) of an ellipse are two points A and B such that for every point P on the boundary of the ellipse, AP + PB is constant. Answer: a21c033d9e119c293e51966ea78c9950 Problem 386 =========== Let n be an integer and S(n) be the set of factors of n. A subset A of S(n) is called an antichain of S(n) if A contains only one element or if none of the elements of A divides any of the other elements of A. For example: S(30) = {1, 2, 3, 5, 6, 10, 15, 30} {2, 5, 6} is not an antichain of S(30). {2, 3, 5} is an antichain of S(30). Let N(n) be the maximum length of an antichain of S(n). Find ΣN(n) for 1 ≤ n ≤ 10^8 Answer: d1d893f7c50910aa10daec5e9352e86d Problem 387 =========== A Harshad or Niven number is a number that is divisible by the sum of its digits. 201 is a Harshad number because it is divisible by 3 (the sum of its digits.) When we truncate the last digit from 201, we get 20, which is a Harshad number. When we truncate the last digit from 20, we get 2, which is also a Harshad number. Let's call a Harshad number that, while recursively truncating the last digit, always results in a Harshad number a right truncatable Harshad number. 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. Now take the number 2011 which is prime. When we truncate the last digit from it we get 201, a strong Harshad number that is also right truncatable. Let's call such primes strong, right truncatable Harshad primes. 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 =========== Consider all lattice points (a,b,c) with 0 ≤ a,b,c ≤ N. 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. You are given that D(1 000 000) = 831909254469114121. Find D(10^10). Give as your answer the first nine digits followed by the last nine digits. Answer: 2bab886c7d98d802d9249c9e12d72c25 Problem 389 =========== An unbiased single 4-sided die is thrown and its value, T, is noted. T unbiased 6-sided dice are thrown and their scores are added together. The sum, C, is noted. C unbiased 8-sided dice are thrown and their scores are added together. The sum, O, is noted. O unbiased 12-sided dice are thrown and their scores are added together. The sum, D, is noted. D unbiased 20-sided dice are thrown and their scores are added together. The sum, I, is noted. Find the variance of I, and give your answer rounded to 4 decimal places. 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. The example triangle has b=2 and c=8. 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, ...}. A game is played by two players. Before the game starts, a number n is chosen. A counter c starts at 0. At each turn, the player chooses a number from 1 to n (inclusive) and increases c by that number. The resulting value of c must be a member of S. If there are no more valid moves, the player loses. 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. Given Σ(M(n))^3 = 8150 for 1 ≤ n ≤ 20. Find Σ(M(n))^3 for 1 ≤ n ≤ 1000. Answer: b2947548d4f5c4878c5f788f9849e750 Problem 392 =========== A rectilinear grid is an orthogonal grid where the spacing between the gridlines does not have to be equidistant. An example of such grid is logarithmic graph paper. Consider rectilinear grids in the Cartesian coordinate system with the following properties: • The gridlines are parallel to the axes of the Cartesian coordinate system. • There are N+2 vertical and N+2 horizontal gridlines. Hence there are (N+1) x (N+1) rectangular cells. • The equations of the two outer vertical gridlines are x = -1 and x = 1. • The equations of the two outer horizontal gridlines are y = -1 and y = 1. • The grid cells are colored red if they overlap with the unit circle, black otherwise. 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. E.g. here is a picture of the solution for N = 10: The area occupied by the red cells for N = 10 rounded to 10 digits behind the decimal point is 3.3469640797. Find the positions for N = 400. Give as your answer the area occupied by the red cells rounded to 10 digits behind the decimal point. 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. You are given that f(4) = 88. Find f(10). Answer: 58e4990838fb3d1725872da30f9db748 Problem 394 =========== Jeff eats a pie in an unusual way. The pie is circular. He starts with slicing an initial cut in the pie along a radius. While there is at least a given fraction F of pie left, he performs the following procedure: - He makes two slices from the pie centre to any point of what is remaining of the pie border, any point on the remaining pie border equally likely. This will divide the remaining pie into three pieces. - Going counterclockwise from the initial cut, he takes the first two pie pieces and eats them. When less than a fraction F of pie remains, he does not repeat this procedure. Instead, he eats all of the remaining pie. 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. Find E(40) rounded to 10 decimal places behind the decimal point. Answer: f8ad575e1a03365a60b6429c3b7a64df Problem 395 =========== The Pythagorean tree is a fractal generated by the following procedure: 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. The resulting figure, after an infinite number of iterations, is the Pythagorean tree. 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. The sequence terminates when g[k] becomes 0. 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. It can be shown that every weak Goodstein sequence terminates. 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. Find the last 9 digits of ΣG(n) for 1 ≤ n < 16. 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. Let F(K, X) be the number of the integer quadruplets (k, a, b, c) such that at least one angle of the triangle ABC is 45-degree, with 1 ≤ k ≤ K and -X ≤ a < b < c ≤ X. For example, F(1, 10) = 41 and F(10, 100) = 12492. Find F(10^6, 10^9). 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. Let E(n, m) be the expected length of the second-shortest segment.For example, E(3, 2) = 2 and E(8, 3) = 16/7.Note that if multiple segments have the same shortest length the length of the second-shortest segment is defined as the same as the shortest length. 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. The 200th squarefree fibonacci number is:971183874599339129547649988289594072811608739584170445. The last sixteen digits of this number are: 1608739584170445 and in scientific notation this number can be written as 9.7e53. Find the 100 000 000th squarefree fibonacci number. Give as your answer its last sixteen digits followed by a comma followed by the number in scientific notation (rounded to one digit after the decimal point). For the 200th squarefree number the answer would have been: 1608739584170445,9.7e53 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 =========== A Fibonacci tree is a binary tree recursively defined as: • T(0) is the empty tree. • T(1) is the binary tree with only one node. • T(k) consists of a root node that has T(k-1) and T(k-2) as children. 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). For example, f(5) = 1 and f(10) = 17. Find f(10000). Give the last 18 digits of your answer. Answer: 60aa790c07af1446c1e2deba72543a1f Problem 401 =========== The divisors of 6 are 1,2,3 and 6. The sum of the squares of these numbers is 1+4+9+36=50. Let sigma2(n) represent the sum of the squares of the divisors of n.Thus sigma2(6)=50. Let SIGMA2 represent the summatory function of sigma2, that is SIGMA2(n)=∑sigma2(i) for i=1 to n. The first 6 values of SIGMA2 are: 1,6,16,37,63 and 113. Find SIGMA2(10^15) modulo 10^9. Answer: 982a249d8b45ef10c98c32dabac00751 Problem 402 =========== It can be shown that the polynomial n^4 + 4n^3 + 2n^2 + 5n is a multiple of 6 for every integer n. It can also be shown that 6 is the largest integer satisfying this property. Define M(a, b, c) as the maximum m such that n^4 + an^3 + bn^2 + cn is a multiple of m for all integers n. For example, M(4, 2, 5) = 6. Also, define S(N) as the sum of M(a, b, c) for all 0 < a, b, c ≤ N. We can verify that S(10) = 1972 and S(10000) = 2024258331114. Let F[k] be the Fibonacci sequence: F[0] = 0, F[1] = 1 and F[k] = F[k-1] + F[k-2] for k ≥ 2. Find the last 9 digits of Σ S(F[k]) for 2 ≤ k ≤ 1234567890123. Answer: fa7ae8e9243f01b0eac10ec5aaff1f42 Problem 403 =========== For integers a and b, we define D(a, b) as the domain enclosed by the parabola y = x^2 and the line y = a·x + b: D(a, b) = { (x, y) | x^2 ≤ y ≤ a·x + b }. L(a, b) is defined as the number of lattice points contained in D(a, b). For example, L(1, 2) = 8 and L(2, -1) = 1. 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. Find S(10^12). Give your answer mod 10^8. Answer: 31c018e3781a3e170366f01e30f09602 Problem 404 =========== E[a] is an ellipse with an equation of the form x^2 + 4y^2 = 4a^2. E[a]' is the rotated image of E[a] by θ degrees counterclockwise around the origin O(0, 0) for 0° < θ < 90°. b is the distance to the origin of the two intersection points closest to the origin and c is the distance of the two other intersection points. We call an ordered triplet (a, b, c) a canonical ellipsoidal triplet if a, b and c are positive integers. For example, (209, 247, 286) is a canonical ellipsoidal triplet. Let C(N) be the number of distinct canonical ellipsoidal triplets (a, b, c) for a ≤ N. It can be verified that C(10^3) = 7, C(10^4) = 106 and C(10^6) = 11845. Find C(10^17). p_404_c_ellipse.gif Answer: 2d1bc4b93bbc19d9e70c5b04338dea2e Problem 405 =========== We wish to tile a rectangle whose length is twice its width. Let T(0) be the tiling consisting of a single rectangle. For n > 0, let T(n) be obtained from T(n-1) by replacing all tiles in the following manner: The following animation demonstrates the tilings T(n) for n from 0 to 5: 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. Find f(10^k) for k = 10^18, give your answer modulo 17^7. 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). Given the value of n, a, and b, an optimal strategy minimizes the total cost for the worst possible case. For example, if n = 5, a = 2, and b = 3, then we may begin by asking "2" as our first question. 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 C(n, a, b) be the worst-case cost achieved by an optimal strategy for the given values of n, a, and b. Here are a few examples: C(5, 2, 3) = 5 C(500, √2, √3) = 13.22073197... C(20000, 5, 7) = 82 C(2000000, √5, √7) = 49.63755955... 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 =========== If we calculate a^2 mod 6 for 0 ≤ a ≤ 5 we get: 0,1,4,3,4,1. The largest value of a such that a^2 ≡ a mod 6 is 4. Let's call M(n) the largest value of a < n such that a^2 ≡ a (mod n). So M(6) = 4. Find ∑M(n) for 1 ≤ n ≤ 10^7. Answer: f4da34a4b357123cb142739a52e010f2 Problem 408 =========== Let's call a lattice point (x, y) inadmissible if x, y and x + y are all positive perfect squares. For example, (9, 16) is inadmissible, while (0, 4), (3, 1) and (9, 4) are not. 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. Find P(10 000 000) mod 1 000 000 007. Answer: 2c09e247c6144c16cae2358d316affd9 Problem 409 =========== Let n be a positive integer. Consider nim positions where: • There are n non-empty piles. • Each pile has size less than 2^n. • No two piles have the same size. Let W(n) be the number of winning nim positions satisfying the aboveconditions (a position is winning if the first player has a winning strategy). For example, W(1) = 1, W(2) = 6, W(3) = 168, W(5) = 19764360 and W(100) mod 1 000 000 007 = 384777056. Find W(10 000 000) mod 1 000 000 007. 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. For example, the quadruplet (r, a, b, c) = (2, 6, 2, -7) satisfies this property. Let F(R, X) be the number of the integer quadruplets (r, a, b, c) with this property, and with 0 < r ≤ R and 0 < a ≤ X. 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 =========== Let n be a positive integer. Suppose there are stations at the coordinates (x, y) = (2^i mod n, 3^i mod n) for 0 ≤ i ≤ 2n. We will consider stations with the same coordinates as the same station. 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: It can also be verified that S(123) = 14 and S(10000) = 48. Find ∑ S(k^5) for 1 ≤ k ≤ 30. 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. For example, L(5, 3) looks like this: We want to number each cell of L(m, n) with consecutive integers 1, 2, 3, ... such that the number in every cell is smaller than the number below it and to the left of it. For example, here are two valid numberings of L(5, 3): Let LC(m, n) be the number of valid numberings of L(m, n). It can be verified that LC(3, 0) = 42, LC(5, 3) = 250250, LC(6, 3) = 406029023400 and LC(10, 5) mod 76543217 = 61251715. Find LC(10000, 5000) mod 76543217. Answer: 8919ccca34b7ccc293d33e06872c668d Problem 413 =========== We say that a d-digit positive number (no leading zeros) is a one-child number if exactly one of its sub-strings is divisible by d. 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. Let F(N) be the number of the one-child numbers less than N. We can verify that F(10) = 9, F(10^3) = 389 and F(10^7) = 277674. Find F(10^19). Answer: 569ad33af889215704df5a9e278aa004 Problem 414 =========== 6174 is a remarkable number; if we sort its digits in increasing order and subtract that number from the number you get when you sort the digits in decreasing order, we get 7641-1467=6174. Even more remarkable is that if we start from any 4 digit number and repeat this process of sorting and subtracting, we'll eventually end up with 6174 or immediately with 0 if all digits are equal. This also works with numbers that have less than 4 digits if we pad the number with leading zeroes until we have 4 digits. E.g. let's start with the number 0837: 8730-0378=8352 8532-2358=6174 6174 is called the Kaprekar constant. The process of sorting and subtracting and repeating this until either 0 or the Kaprekar constant is reached is called the Kaprekar routine. 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 • 0 if i = C[b] or if i written in base b consists of 5 identical digits • the number of iterations it takes the Kaprekar routine in base b to arrive at C[b], otherwise 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. Define S(b) as the sum of sb(i) for 0 < i < b^5. E.g. S(15) = 5274369 S(111) = 400668930299 Find the sum of S(6k+3) for 2 ≤ k ≤ 300. Give the last 18 digits as your answer. Answer: 42f095bdfd71e1ae4ae0ceead1bb1802 Problem 415 =========== A set of lattice points S is called a titanic set if there exists a line passing through exactly two points in S. 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. Find T(10^11) mod 10^8. Answer: 2357ad217832274f444cae2a6580b193 Problem 416 =========== A row of n squares contains a frog in the leftmost square. By successive jumps the frog goes to the rightmost square and then back to the leftmost square. On the outward trip he jumps one, two or three squares to the right, and on the homeward trip he jumps to the left in a similar manner. He cannot jump outside the squares. He repeats the round-trip travel m times. Let F(m, n) be the number of the ways the frog can travel so that at most one square remains unvisited. For example, F(1, 3) = 4, F(1, 4) = 15, F(1, 5) = 46, F(2, 3) = 16 and F(2, 100) mod 10^9 = 429619151. Find the last 9 digits of F(10, 10^12). Answer: 6f398386fdfec57ac166d4970c2bcad2 Problem 417 =========== A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given: 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. Find ∑L(n) for 3 ≤ n ≤ 100 000 000 Answer: 93a7df08c972f1e7788516d056a7e016 Problem 418 =========== Let n be a positive integer. An integer triple (a, b, c) is called a factorisation triple of n if: • 1 ≤ a ≤ b ≤ c • a·b·c = n. Define f(n) to be a + b + c for the factorisation triple (a, b, c) of n which minimises c / a. One can show that this triple is unique. For example, f(165) = 19, f(100100) = 142 and f(20!) = 4034872. Find f(43!). 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. Find A(n), B(n) and C(n) for n = 10^12. Give your answer modulo 2^30 and separate your values for A, B and C by a comma. E.g. for n = 40 the answer would be 31254,20259,11625 Answer: b27db655498b3d64ad4338fcdc9d178f Problem 420 =========== A positive integer matrix is a matrix whose elements are all positive integers. Some positive integer matrices can be expressed as a square of a positive integer matrix in two different ways. Here is an example: 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. E.g. 2^15+1 = 3×3×11×331. So s(2,10) = 3 and s(2,1000) = 3+11+331 = 345. Also 10^15+1 = 7×11×13×211×241×2161×9091. So s(10,100) = 31 and s(10,1000) = 483. Find ∑ s(n,10^8) for 1 ≤ n ≤ 10^11. Answer: 481fcc5ff16ccf1645fb136c123ed660 Problem 422 =========== Let H be the hyperbola defined by the equation 12x^2 + 7xy - 12y^2 = 625. Next, define X as the point (7, 1). It can be seen that X is in H. Now we define a sequence of points in H, {P[i] : i ≥ 1}, as: • P[1] = (13, 61/4). • P[2] = (-43/6, -4). • For i > 2, P[i] is the unique point in H that is different from P[i-1] and such that line P[i]P[i-1] is parallel to line P[i-2]X. It can be shown that P[i] is well-defined, and that its coordinates are always rational. You are given that P[3] = (-19/2, -229/24), P[4] = (1267/144, -37/12) and P[7] = (17194218091/143327232, 274748766781/1719926784). Find P[n] for n = 11^14 in the following format: If P[n] = (a/b, c/d) where the fractions are in lowest terms and the denominators are positive, then the answer is (a + b + c + d) mod 1 000 000 007. For n = 7, the answer would have been: 806236837. Answer: 7034610688a8851f742f912143c1becf Problem 423 =========== Let n be a positive integer. A 6-sided die is thrown n times. Let c be the number of pairs of consecutive throws that give the same value. For example, if n = 7 and the values of the die throws are (1,1,5,6,6,6,3), then the following pairs of consecutive throws give the same value: (1,1,5,6,6,6,3) (1,1,5,6,6,6,3) (1,1,5,6,6,6,3) Therefore, c = 3 for (1,1,5,6,6,6,3). Define C(n) as the number of outcomes of throwing a 6-sided die n times such that c does not exceed π(n).^1 For example, C(3) = 216, C(4) = 1290, C(11) = 361912500 and C(24) = 4727547363281250000. Define S(L) as ∑ C(n) for 1 ≤ n ≤ L. For example, S(50) mod 1 000 000 007 = 832833871. Find S(50 000 000) mod 1 000 000 007. ^1 π denotes the prime-counting function, i.e. π(n) is the number of primes ≤ n. Answer: e2add9d46ebd8ba59a07dca791cd629b Problem 424 =========== The above is an example of a cryptic kakuro (also known as cross sums, or even sums cross) puzzle, with its final solution on the right. (The common rules of kakuro puzzles can be found easily on numerous internet sites. Other related information can also be currently found at [1]krazydad.com whose author has provided the puzzle data for this challenge.) The downloadable text file ([2]kakuro200.txt) contains the description of 200 such puzzles, a mix of 5x5 and 6x6 types. The first puzzle in the file is the above example which is coded as follows: 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 first character is a numerical digit indicating the size of the information grid. It would be either a 6 (for a 5x5 kakuro puzzle) or a 7 (for a 6x6 puzzle) followed by a comma (,). The extra top line and left column are needed to insert information. 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 description of the last cell is followed by a Carriage Return/Line Feed (CRLF) instead of 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. Find the sum of the answers for the 200 puzzles. 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. We call a prime P a 2's relative if there exists a chain of connected primes between 2 and P and no prime in the chain exceeds P. 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. A turn consists of moving each ball exactly once according to the following rule: Transfer the leftmost ball which has not been moved to the nearest empty box to its right. After one turn the sequence (2, 2, 2, 1, 2) becomes (2, 2, 1, 2, 3) as can be seen below; note that we begin the new sequence starting at the first occupied box. A system like this is called a Box-Ball System or BBS for short. It can be shown that after a sufficient number of turns, the system evolves to a state where the consecutive numbers of occupied boxes is invariant. In the example below, the consecutive numbers of occupied boxes evolves to [1, 2, 3]; we shall call this the final state. We define the sequence {t[i]}: • 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 =========== A sequence of integers S = {s[i]} is called an n-sequence if it has n elements and each element s[i] satisfies 1 ≤ s[i] ≤ n. Thus there are n^n distinct n-sequences in total.For example, the sequence S = {1, 5, 5, 10, 7, 7, 7, 2, 3, 7} is a 10-sequence. 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. Let f(n) = ∑ L(S) for all n-sequences S. For example, f(3) = 45, f(7) = 1403689 and f(11) = 481496895121. Find f(7 500 000) mod 1 000 000 009. Answer: ecb4da2c940b517c63d8d256814dd511 Problem 428 =========== Let a, b and c be positive numbers. Let W, X, Y, Z be four collinear points where |WX| = a, |XY| = b, |YZ| = c and |WZ| = a + b + c. Let C[in] be the circle having the diameter XY. Let C[out] be the circle having the diameter WZ. The triplet (a, b, c) is called a necklace triplet if you can place k ≥ 3 distinct circles C[1], C[2], ..., C[k] such that: • 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. Find T(1 000 000 000). Answer: c6010c109b66b34bf3594e63eb58b446 Problem 429 =========== A unitary divisor d of a number n is a divisor of n that has the property gcd(d, n/d) = 1. The unitary divisors of 4! = 24 are 1, 3, 8 and 24. The sum of their squares is 1^2 + 3^2 + 8^2 + 24^2 = 650. Let S(n) represent the sum of the squares of the unitary divisors of n. Thus S(4!)=650. Find S(100 000 000!) modulo 1 000 000 009. Answer: ec4f87b0c01680e951326d9e85d2c03f Problem 430 =========== N disks are placed in a row, indexed 1 to N from left to right. Each disk has a black side and white side. Initially all disks show their white side. At each turn, two, not necessarily distinct, integers A and B between 1 and N (inclusive) are chosen uniformly at random. All disks with an index from A to B (inclusive) are flipped. 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. Find E(10^10, 4000). Give your answer rounded to 2 decimal places behind the decimal point. 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. We shall let the amount of space wasted in cubic metres be given by $V(x)$. If $x = 1.114785284$, which happens to have three squared decimal places, then the amount of space wasted, $V(1.114785284) \approx 36$. Given the range of possible solutions to this problem there is exactly one other option: $V(2.511167869) \approx 49$. It would be like knowing that the square is king of the silo, sitting in splendid glory on top of your grain. Fred's eyes light up with delight at this elegant resolution, but on closer inspection of Quentin's drawings and calculations his happiness turns to despondency once more. Fred points out to Quentin that it's the radius of the silo that is 6 metres, not the diameter, and the angle of repose for his grain is 40 degrees. However, if Quentin can find a set of solutions for this particular silo then he will be more than happy to keep it. If Quick thinking Quentin is to satisfy frustratingly fussy Fred the farmer's appetite for all things square then determine the values of $x$ for all possible square space wastage options and calculate $\sum x$ correct to 9 decimal places. p_431_grain_silo.png Answer: 5e5d81aa8bfaf92f68cdef0154c5c238 Problem 432 =========== Let S(n,m) = ∑φ(n × i) for 1 ≤ i ≤ m. (φ is Euler's totient function) You are given that S(510510,10^6 )= 45480596821125120. Find S(510510,10^11). Give the last 9 digits of your answer. Answer: e171c2872d650e47589842faa80f5707 Problem 433 =========== Let E(x[0], y[0]) be the number of steps it takes to determine the greatest common divisor of x[0] and y[0] with Euclid's algorithm. More formally: x[1] = y[0], y[1] = x[0] mod y[0] x[n] = y[n-1], y[n] = x[n-1] mod y[n-1] E(x[0], y[0]) is the smallest n such that y[n] = 0. We have E(1,1) = 1, E(10,6) = 3 and E(6,10) = 4. Define S(N) as the sum of E(x,y) for 1 ≤ x,y ≤ N. We have S(1) = 1, S(10) = 221 and S(100) = 39826. Find S(5·10^6). Answer: 0eeca9fa5cf25a2bfae01f1f04d6cd35 Problem 434 =========== Recall that a graph is a collection of vertices and edges connecting the vertices, and that two vertices connected by an edge are called adjacent. Graphs can be embedded in Euclidean space by associating each vertex with a point in the Euclidean space. A flexible graph is an embedding of a graph where it is possible to move one or more vertices continuously so that the distance between at least two nonadjacent vertices is altered while the distances between each pair of adjacent vertices is kept constant. A rigid graph is an embedding of a graph which is not flexible. Informally, a graph is rigid if by replacing the vertices with fully rotating hinges and the edges with rods that are unbending and inelastic, no parts of the graph can be moved independently from the rest of the graph. 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 Define S(N) as ∑R(i,j) for 1 ≤ i, j ≤ N. E.g. S(5) = 25021721. Find S(100), give your answer modulo 1000000033 Answer: f51d9fd41a8ce217682321a020be6fec Problem 435 =========== The Fibonacci numbers {f[n], n ≥ 0} are defined recursively as f[n] = f[n-1] + f[n-2] with base cases f[0] = 0 and f[1] = 1. Define the polynomials {F[n], n ≥ 0} as F[n](x) = ∑f[i]x^i for 0 ≤ i ≤ n. For example, F[7](x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7, and F[7](11) = 268357683. Let n = 10^15. Find the sum [∑[0≤x≤100] F[n](x)] mod 1307674368000 (= 15!). Answer: 0f08231a97e872f565a085de75743a1c Problem 436 =========== Julie proposes the following wager to her sister Louise. She suggests they play a game of chance to determine who will wash the dishes. For this game, they shall use a generator of independent random numbers uniformly distributed between 0 and 1. The game starts with S = 0. The first player, Louise, adds to S different random numbers from the generator until S > 1 and records her last random number 'x'. The second player, Julie, continues adding to S different random numbers from the generator until S > 2 and records her last random number 'y'. The player with the highest number wins and the loser washes the dishes, i.e. if y > x the second player wins. 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 =========== When we calculate 8^n modulo 11 for n=0 to 9 we get: 1, 8, 9, 6, 4, 10, 3, 2, 5, 7. As we see all possible values from 1 to 10 occur. So 8 is a primitive root of 11. But there is more: If we take a closer look we see: 1+8=9 8+9=17≡6 mod 11 9+6=15≡4 mod 11 6+4=10 4+10=14≡3 mod 11 10+3=13≡2 mod 11 3+2=5 2+5=7 5+7=12≡1 mod 11. 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: • x[1], ..., x[n] are all real. • If x[1], ..., x[n] are sorted, ⌊x[i]⌋ = i for 1 ≤ i ≤ n. (⌊·⌋: floor function.) In the case of n = 4, there are 12 n-tuples of integers which satisfy both conditions. We define S(t) as the sum of the absolute values of the integers in t. For n = 4 we can verify that ∑S(t) = 2087 for all n-tuples t which satisfy both conditions. Find ∑S(t) for n = 7. Answer: ? Problem 439 =========== Let d(k) be the sum of all divisors of k. We define the function S(N) = ∑[1≤i≤N] ∑[1≤j≤N] d(i·j). For example, S(3) = d(1) + d(2) + d(3) + d(2) + d(4) + d(6) + d(3) + d(6) + d(9) = 59. 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 =========== We want to tile a board of length n and height 1 completely, with either 1 × 2 blocks or 1 × 1 blocks with a single decimal digit on top: For example, here are some of the ways to tile a board of length n = 8: Let T(n) be the number of ways to tile a board of length n as described above. For example, T(1) = 10 and T(2) = 101. Let S(L) be the triple sum ∑[a,b,c] gcd(T(c^a), T(c^b)) for 1 ≤ a, b, c ≤ L. For example: S(2) = 10444 S(3) = 1292115238446807016106539989 S(4) mod 987 898 789 = 670616280. Find S(2000) mod 987 898 789. Answer: ? 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. We also define S(N) as the sum of R(i) for 2 ≤ i ≤ N. We can verify that S(2) = R(2) = 1/2, S(10) ≈ 6.9147 and S(100) ≈ 58.2962. Find S(10^7). Give your answer rounded to four decimal places. Answer: 152cc265f5461c5055db95a122280416 Problem 442 =========== An integer is called eleven-free if its decimal expansion does not contain any substring representing a power of 11 except 1. 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 =========== Let g(n) be a sequence defined as follows: g(4) = 13, g(n) = g(n-1) + gcd(n, g(n-1)) for n > 4. The first few values are: 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 =========== A group of p people decide to sit down at a round table and play a lottery-ticket trading game. Each person starts off with a randomly-assigned, unscratched lottery ticket. Each ticket, when scratched, reveals a whole-pound prize ranging anywhere from £1 to £p, with no two tickets alike. The goal of the game is for each person to maximize his ticket winnings upon leaving the game. An arbitrary person is chosen to be the first player. Going around the table, each player has only one of two options: 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). Let S[1](N) = E(p) Let S[k](N) = S[k-1](p) for k > 1 Find S[20](10^14) and write the answer in scientific notation rounded to 10 significant digits. Use a lowercase e to separate mantissa and exponent (e.g. S[3](100) = 5.983679014e5). Answer: e6745c386ba3c0de1bf56897e453c7c8 Problem 445 =========== For every integer n>1, the family of functions f[n,a,b] is defined by f[n,a,b](x)≡ax+b mod n for a,b,x integer and 01, the family of functions f[n,a,b] is defined by f[n,a,b](x)≡ax+b mod n for a,b,x integer and 01, the family of functions f[n,a,b] is defined by f[n,a,b](x)≡ax+b mod n for a,b,x integer and 0 1). Here are the possible seating arrangements for N = 15: 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. Also, ∑f(N) = 83 for 1 ≤ N ≤ 20 and ∑f(N) = 13343 for 1 ≤ N ≤ 500. Find ∑f(N) for 1 ≤ N ≤ 10^12. Give the last 8 digits of your answer. Answer: ? Problem 473 =========== Let $\varphi$ be the golden ratio: $\varphi=\frac{1+\sqrt{5}}{2}.$ Remarkably it is possible to write every positive integer as a sum of powers of $\varphi$ even if we require that every power of $\varphi$ is used at most once in this sum. Even then this representation is not unique. We can make it unique by requiring that no powers with consecutive exponents are used and that the representation is finite. E.g: $2=\varphi+\varphi^{-2}$ and $3=\varphi^{2}+\varphi^{-2}$ To represent this sum of powers of $\varphi$ we use a string of 0's and 1's with a point to indicate where the negative exponents start. We call this the representation in the phigital numberbase. So $1=1_{\varphi}$, $2=10.01_{\varphi}$, $3=100.01_{\varphi}$ and $14=100100.001001_{\varphi}$. The strings representing 1, 2 and 14 in the phigital number base are palindromic, while the string representating 3 is not. (the phigital point is not the middle character). 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. Find F(10^6!, 65432) modulo (10^16 + 61). 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. Find f(600) mod 1 000 000 007. Answer: 6be2411783d9ca8e7ad174b269a85be5 Problem 476 =========== Let R(a, b, c) be the maximum area covered by three non-overlapping circles inside a triangle with edge lengths a, b and c. 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 You are given S(2) = R(1, 1, 1) ≈ 0.31998, S(5) ≈ 1.25899. Find S(1803) rounded to 5 decimal places behind the decimal point. Answer: 4d6a99b2a0f22af561aeeb69c0126fef