Hint for Project Euler Problem 19 Counting Sundays

By -

Tags: #Project Euler without coding series #junior high maths
Counting Sundays

Problem 19

You are given the following information, but you may prefer to do some research for yourself.
1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Let's take a break from the latest brain-drilling problems and take a look at some rather simple issues. As you can see from the tags, we will do this without coding.
------------------------------------------------------
Method 1

Tool: Paper, pen
31 days mod 7 = 3 days
30 days mod 7 = 2 days
29 days mod 7 = 1 days
28 days mod 7 = 0 days
If assign Mon = 1, Tue = 2, ... , Sat = 6, Sun = 0; we have the table listed as below:
Non Leap Year

Jan(+3) Feb(+0) Mar(+3) Apr(+2) May(+3) Jun(+2) Jul(+3) Aug(+3) Sep(+2) Oct(+3) Nov(+2) Dec(+3)

1 4 4 0 2 5 0 3 6 1 4 6 -> If Jan 1st is Mon, then we have 2 Sundays fell on the 1st of month, Apr & Jul;

2 5 5 1 3 6 1 4 0 2 5 0 -> If Jan 1st is Tue, then we have 2 Sundays fell on the 1st of month, Sep & Dec;

3 6 6 2 4 0 2 5 1 3 6 1 -> If Jan 1st is Wed, then we have 1 Sundays fell on the 1st of month, Jun;

4 0 0 3 5 1 3 6 2 4 0 2 -> If Jan 1st is Thur, then we have 3 Sundays fell on the 1st of month, Feb,Mar,Nov;

5 1 1 4 6 2 4 0 3 5 1 3 -> If Jan 1st is Fri, then we have 1 Sundays fell on the 1st of month, Aug;

6 2 2 5 0 3 5 1 4 6 2 4 -> If Jan 1st is Sat, then we have 1 Sundays fell on the 1st of month, May;

0 3 3 6 1 4 6 2 5 0 3 5 -> If Jan 1st is Sun, then we have 2 Sundays fell on the 1st of month, Jan & Oct;

Leap Year
Since,
Non-leap year
Since (5,7)=1
Altogether, 3x3+1 = 10 groups of (0123456) + (23450)
Similar for the 25 leap years, (2000 mod 400 = 0, 2000 is a leap year), we started at
Since (5,7)=1
Altogether, 3 groups of (0123456) + (6420)
Using the table to count Sundays, we have the below equation.
Method 2
Jan(+3) Feb(+1) Mar(+3) Apr(+2) May(+3) Jun(+2) Jul(+3) Aug(+3) Sep(+2) Oct(+3) Nov(+2) Dec(+3)
1 4 5 1 3 6 1 4 0 2 5 0 -> If Jan 1st is Mon, then we have 2 Sundays fell on the 1st of month;

2 5 6 2 4 0 2 5 1 3 6 1 -> If Jan 1st is Tue, then we have 1 Sundays fell on the 1st of month;

3 6 0 3 5 1 3 6 2 4 0 2 -> If Jan 1st is Wed, then we have 2 Sundays fell on the 1st of month;

4 0 1 4 6 2 4 0 3 5 1 3 -> If Jan 1st is Thur, then we have 2 Sundays fell on the 1st of month;

5 1 2 5 0 3 5 1 4 6 2 4 -> If Jan 1st is Fri, then we have 1 Sundays fell on the 1st of month;

6 2 3 6 1 4 6 2 5 0 3 5 -> If Jan 1st is Sat, then we have 1 Sundays fell on the 1st of month;

0 3 4 0 2 5 0 3 6 1 4 6 -> If Jan 1st is Sun, then we have 3 Sundays fell on the 1st of month;

365 days mod 7 = 1 day
366 days mod 7 = 2 days

1901/01/01 -> 2
1902/01/01 -> 3
1903/01/01 -> 4
+3
1905/01/01 -> 0
1906/01/01 -> 1
1907/01/01 -> 2
...

We can see the pattern that (234,012,560,345,123,601,456) forms a group of 21 non-leap years which have 3 x (0123456) for Jan 1st.

It repeated 3 times to cover 21x3 = 63 non leap years.
The rest 12 non leap years are (234,012,560,345)

1904/01/01 -> 6
+5
1908/01/01 -> 4
...

We can see the pattern that (5,3,1,6,4,2,0) forms a group of 7 leap years which have 1 x (0123456) for Jan 1st.

It repeated 3 times to cover 7x3 = 21 leap years.
The rest 4 non leap years are (5,3,1,6)
10 x 12 + (2+1+3+1+2) + 3 x 12 + (1+2+2+1) = 12 x 13 + 9 + 6 = 144 + 12 + 15 = 171
-----------------------------------------------------
Method 2

Tool: Excel Spreadsheet
It is just 12 x 100 = 1200 months. With Excel functions, it is easy to count all Sundays within those 1200 days.

-----------------------------------------------------
Method 3
Tool: A lucky guess
1200 / 7 = 171.4
---------------------
The opinion above is original and unproven work. Please correct me if I made a mistake.

Comments

  1. UnknownMay 3, 2018 at 12:57 AM

    "It is just 12 x 100 = 1200 days." no it's 12 x 100 = 1200 months.

    ReplyDelete

Post a Comment

Popular posts from this blog

Project Euler Problem 684 Inverse Digit Sum - Solution

By Brownie -
Image
This one is relatively straight forward. Below is a solution in python and will give us correct answer within reasonable amount of time. (Generally, if python can calculate this fast enough, I am happy with the solution, nothing against python...) modulo = 1000000007 #speed up hint: (10e9) % modulo = -7 #init speedup array shortcut = 18 arr_lookup = [ 1 ] * (shortcut + 1 ) for i in range ( 1 ,(shortcut + 1 )): arr_lookup[i] = ( 10 ** i) % modulo def S (i): A = i % 9 B = i // 9 #sum = (1+..+A)*(10^B) + A*(10^B-1) + 45*(10^(B-1)) + 9*(10^(B-1)-1) + 45*(10^(B-2)) + 9*(10^(B-2)-1) + ... + 45*10 + 9*9 +45 #sum = (A(A+1)/2)*(10^B) + A*(10^B) - A +(9+45)*(10^(B-1) + .. + 1) - 9*B #sum = (10^B) * (A(A+1)/2 + A) - A - 9*B + 6*(10-1)*(10^(B-1) + .. + 1) = (10^B) * (A(A+1)/2 + A) - A - 9*B + 6*(10^B -1) #sum = (10^B) * (A(A+1)/2 + A + 6) - (A + 9*B + 6) #since (7,10e9+7)=1; 7^(10e9+7 - 1)%(10^9+7)=1 #B = 18C+R C = B ...
Read more

Project Euler Problem 686 Powers of Two - Solution

By Brownie -
Image
Powers of Two     Problem 686 2 7 = 128 2 7 = 128  is the first power of two whose leading digits are "12". The next power of two whose leading digits are "12" is  2 80 2 80 . Define  p ( L , n ) p ( L , n )  to be the  n n th-smallest value of  j j  such that the base 10 representation of  2 j 2 j  begins with the digits of  L L . So  p ( 12 , 1 ) = 7 p ( 12 , 1 ) = 7  and  p ( 12 , 2 ) = 80 p ( 12 , 2 ) = 80 . You are also given that  p ( 123 , 45 ) = 12710 p ( 123 , 45 ) = 12710 . Find  p ( 123 , 678910 ) p ( 123 , 678910 ) . Test the first 3 digits of a large number is quite costly.  So first thing first, think log(). --------------------- import math lowerbound = math.log(1.23,10) upperbound = math.log(1.24,10) def testlog(i): logi = math.log(2,10)*i diff = (logi - int(logi)) return diff We only care about the part after decimal point, thus  dif...
Read more

Project Euler Problem 717 Summation of a Modular Formula - Solution

By Brownie -
Image
Summation of a Modular Formula          Problem 717 For an odd prime  p p , define  f ( p ) = ⌊ 2 ( 2 p ) p ⌋ mod 2 p f ( p ) = ⌊ 2 ( 2 p ) p ⌋ mod 2 p For example, when  p = 3 p = 3 ,  ⌊ 2 8 / 3 ⌋ = 85 ≡ 5 ( mod 8 ) ⌊ 2 8 / 3 ⌋ = 85 ≡ 5 ( mod 8 )  and so  f ( 3 ) = 5 f ( 3 ) = 5 . Further define  g ( p ) = f ( p ) mod p g ( p ) = f ( p ) mod p . You are given  g ( 31 ) = 17 g ( 31 ) = 17 . Now define  G ( N ) G ( N )  to be the summation of  g ( p ) g ( p )  for all odd primes less than  N N . You are given  G ( 100 ) = 474 G ( 100 ) = 474  and  G ( 10 4 ) = 2819236 G ( 10 4 ) = 2819236 . Find  G ( 10 7 ) This problem is not really that complicated to reduce to acceptable execution time. (Python, ~8hrs in 1 thread on a typical laptop.) Please leave a comment if you have better solution or suggestion. See note below. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17...
Read more