Automated Matrix Multiplication

Computer Science Level 4

A = [ 560 532 442 389 51 690 478 12 209 263 155 608 89 466 730 835 ] A = \begin{bmatrix} 560 & 532 & 442 & 389 \\ 51 & 690 & 478 & 12 \\ 209 & 263 & 155 & 608 \\ 89 & 466 & 730 & 835 \end{bmatrix}

Consider the matrix above.

Let S S be the sum of all the entries in A 100 A^{100} . Find the sum of digits of S S


The answer is 1434.

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
-- defining rows as lists of elements, and matrices as lists of rows
type Row a = [a]
type Matrix a = [Row a]

-- functions returning the rows of a matrix and columns, by computing it's transpose
rows :: Matrix a -> Matrix a
rows = id
cols :: Matrix a -> Matrix a
cols [xs] = [[x] | x <- xs] -- each row contains each element of the matrix
cols (xs:xss) = zipWith (:) xs (cols xss) --transpose one row and affix it to the transposition of others

innerProduct :: Num a => Row a -> Row a -> a
innerProduct a b = sum $ zipWith (*) a b

mult :: Num a => Matrix a -> Matrix a -> Matrix a
mult [] _ = []
mult _ [] = []
mult (xs:xss) b = [(map (innerProduct xs) (cols b))] ++ xss `mult` b -- defining the product row by row

addDigits :: Integer -> Integer
addDigits 0 = 0
addDigits x = addDigits (x `div` 10) + (x `mod` 10)

myMatrix = [[560, 532, 442, 389], [51, 690, 478, 12], [209, 263, 155, 608], [89, 466, 730, 835]]

main = putStrLn $ show.addDigits.sum.concat $ iterate (mult myMatrix) (myMatrix) !! 99

2 Helpful 0 Interesting 0 Brilliant 0 Confused

How do you prove that your answer is correct?

Janardhanan Sivaramakrishnan - 4 years, 10 months ago

Log in to reply

I would have to show that my program does indeed what it claims to be doing. Is that what you want?

Agnishom Chattopadhyay - 4 years, 10 months ago

Log in to reply

It is quite easy to come up with the logic to sum up the digits of the elements of a matrix. However, if the numbers of hundreds of digits long, how do you ensure precision? This is the point that I am ignorant about.

Janardhanan Sivaramakrishnan - 4 years, 10 months ago

Log in to reply

@Janardhanan Sivaramakrishnan – In haskell , Integer can ensure precision for large integers, different from Int .

展豪 張 - 4 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...