♦ IMO 1975 ♦ → Modular Arithmetic → Logarithmic Estimation of Size → Number Theory
◘ Problem 4 : When 4444⁴⁴⁴⁴ is written in decimal notation, the sum of its digits is A. Let B be the sum of the digits of A . Find the sum of the digits of B. ( A and B are written in Decimal Notation )
► Solution : • Note, the number 4444⁴⁴⁴⁴ is really big .
• The number of digits in any number 'X' written in decimal notation is given as : 10ᵃ ≤ X ≤ 10ᵇ => a ≤ log X ≤ b [ where 'a' and 'b' ∈ N₀ ] => Number of digits of 'X' is : ( a + 1 )
→ Number of digits of 4444⁴⁴⁴⁴ is given by : • 4444⁴⁴⁴⁴ < 10000⁴⁴⁴⁴ = 10¹⁷⁷⁷⁶ => Number of digits in 'X' is lesser than 17776 ( approx. 16211 ) => A < 16211 • 9 => A < 145899 => Sum of digits of 'A' is maximum when A = 99999 => B ≤ 45
→ Sum of digits of 'B' is maximum at B = 39 , i.e., 12 => B ≤ 12 ____________________________________________________________
◙ Main Step is to figure out, " The remainder of the sum of digits of any natural number 'X' is the same as the remainder when 'X' is divided by 9 "
◙ Mathematically interpreted as : → If S( x ) defines the sum of digits of x : • X ≡ S( x ) ≡ S( S( x )) ( mod 9 )
→ Proof : • X = A₀ x 10ᵃ¹ + A₁ x 10ᵃ² + ... + A x 10ᵃⁿ But, 10 ≡ 1 ( mod 9 ) => X ≡ A₀ x 1 + A₁ x 1 + ... + A = S ( X ) mod 9 ____________________________________________________________
◘ Coming back to our problem : → 4444⁴⁴⁴⁴ ≡ 4444³ ⁽ ¹⁴⁸¹ ⁾ x 4444 ≡ 4444 ≡ 7 ( mod 9 )
• Now, since S( B ) ≤ 12 and S( B ) ≡ 7 ( mod 9 ) => S( B ) = 7 _____________________________________________________________
→ Hence, the solution to this question was '7' → Additionally, this question was quite troublesome back then, but thanks to modular arithmetic, it consumes less time and space _____________________________________________________________
• A healthy discussion here : → https://math.stackexchange.com/questions/169797 might be just helpful
Answers & Comments
♦ IMO 1975 ♦
→ Modular Arithmetic
→ Logarithmic Estimation of Size
→ Number Theory
◘ Problem 4 : When 4444⁴⁴⁴⁴ is written in decimal notation, the sum of its digits is A. Let B be the sum of the digits of A . Find the sum of the digits of B. ( A and B are written in Decimal Notation )
► Solution :
• Note, the number 4444⁴⁴⁴⁴ is really big .
• The number of digits in any number 'X' written in decimal notation is given as : 10ᵃ ≤ X ≤ 10ᵇ
=> a ≤ log X ≤ b [ where 'a' and 'b' ∈ N₀ ]
=> Number of digits of 'X' is : ( a + 1 )
→ Number of digits of 4444⁴⁴⁴⁴ is given by :
• 4444⁴⁴⁴⁴ < 10000⁴⁴⁴⁴ = 10¹⁷⁷⁷⁶
=> Number of digits in 'X' is lesser than 17776 ( approx. 16211 )
=> A < 16211 • 9
=> A < 145899
=> Sum of digits of 'A' is maximum when A = 99999
=> B ≤ 45
→ Sum of digits of 'B' is maximum at B = 39 , i.e., 12
=> B ≤ 12
____________________________________________________________
◙ Main Step is to figure out, " The remainder of the sum of digits of any natural number 'X' is the same as the remainder when 'X' is divided by 9 "
◙ Mathematically interpreted as :
→ If S( x ) defines the sum of digits of x :
• X ≡ S( x ) ≡ S( S( x )) ( mod 9 )
→ Proof :
• X = A₀ x 10ᵃ¹ + A₁ x 10ᵃ² + ... + A x 10ᵃⁿ
But, 10 ≡ 1 ( mod 9 )
=> X ≡ A₀ x 1 + A₁ x 1 + ... + A = S ( X ) mod 9
____________________________________________________________
◘ Coming back to our problem :
→ 4444⁴⁴⁴⁴ ≡ 4444³ ⁽ ¹⁴⁸¹ ⁾ x 4444 ≡ 4444 ≡ 7 ( mod 9 )
• Now, since S( B ) ≤ 12 and S( B ) ≡ 7 ( mod 9 )
=> S( B ) = 7
_____________________________________________________________
→ Hence, the solution to this question was '7'
→ Additionally, this question was quite troublesome back then, but thanks to modular arithmetic, it consumes less time and space
_____________________________________________________________
• A healthy discussion here :
→ https://math.stackexchange.com/questions/169797
might be just helpful
→ http://www.math.wayne.edu/~brcs/POTW/archives/W12/Prob10SOL.pdf
____________________________________________________________
^_^ Hope this helps
ans= 5.103632503725508048204E16210