<reponame>bhavinjawade/project-euler-solutions<filename>code/permuted_matrices/sol_559.py

# -*- coding: utf-8 -*-
'''
    File name: code\permuted_matrices\sol_559.py
    Author: <NAME>
    Date created: Oct 20, 2018
    Python Version: 3.x
'''

# Solution to Project Euler Problem #559 :: Permuted Matrices
# 
# For more information see:
# https://projecteuler.net/problem=559

# Problem Statement 
'''
An ascent of a column j in a matrix occurs if the value of column j is smaller than the value of column j+1 in all rows.

Let P(k, r, n) be the number of r x n matrices with the following properties:

The rows are permutations of {1, 2, 3, ... , n}.
 Numbering the first column as 1, a column ascent occurs at column j<n if and only if j is not a multiple of k.

For example, P(1, 2, 3) = 19, P(2, 4, 6) = 65508751 and  P(7, 5, 30) mod 1000000123 = 161858102.

Let Q(n) =$\,  \displaystyle \sum_{k=1}^n\,$ P(k, n, n).
For example, Q(5) = 21879393751 and Q(50) mod 1000000123 = 819573537.

Find Q(50000) mod 1000000123.
'''

# Solution 

# Solution Approach 
'''
'''

# -*- coding: utf-8 -*-
'''
    File name: code\permuted_matrices\sol_559.py
    Author: <NAME>
    Date created: Oct 20, 2018
    Python Version: 3.x
'''

# Solution to Project Euler Problem #559 :: Permuted Matrices
# 
# For more information see:
# https://projecteuler.net/problem=559

# Problem Statement 
'''
An ascent of a column j in a matrix occurs if the value of column j is smaller than the value of column j+1 in all rows.

Let P(k, r, n) be the number of r x n matrices with the following properties:

The rows are permutations of {1, 2, 3, ... , n}.
 Numbering the first column as 1, a column ascent occurs at column j<n if and only if j is not a multiple of k.

For example, P(1, 2, 3) = 19, P(2, 4, 6) = 65508751 and  P(7, 5, 30) mod 1000000123 = 161858102.

Let Q(n) =$\,  \displaystyle \sum_{k=1}^n\,$ P(k, n, n).
For example, Q(5) = 21879393751 and Q(50) mod 1000000123 = 819573537.

Find Q(50000) mod 1000000123.
'''

# Solution 

# Solution Approach 
'''
'''
# -*- coding: utf-8 -*- File name: code\permuted_matrices\sol_559.py     Author: <NAME>     Date created: Oct 20, 2018     Python Version: 3.x # Solution to Project Euler Problem #559 :: Permuted Matrices # # For more information see: # https://projecteuler.net/problem=559 # Problem Statement An ascent of a column j in a matrix occurs if the value of column j is smaller than the value of column j+1 in all rows.  Let P(k, r, n) be the number of r x n matrices with the following properties:  The rows are permutations of {1, 2, 3, ... , n}.  Numbering the first column as 1, a column ascent occurs at column j<n if and only if j is not a multiple of k.  For example, P(1, 2, 3) = 19, P(2, 4, 6) = 65508751 and  P(7, 5, 30) mod 1000000123 = 161858102.  Let Q(n) =$\,  \displaystyle \sum_{k=1}^n\,$ P(k, n, n). For example, Q(5) = 21879393751 and Q(50) mod 1000000123 = 819573537.  Find Q(50000) mod 1000000123. # Solution # Solution Approach