Problem 3: Factorials

Points:

Small Case: 10 Answer: 11

Large Case: 20 Answer: 590030438399

Given n, Let a1+a2+a3+...+ak = n!, where a1, a2, ..., ak are consecutive positive integers with k>1.

Let {k,a1,a2,..,ak} be any set. Find number of different such sets.

The problem statement has been updated.
a1, a2, a3... ak can only be positive integers.

Small Case: n = 7

Large Case: n = 77

Solution:

Number of ways of representing a number M as sum of one or more consecutive integers is equal to the number of odd positive divisors of M.

Considering representation as sum of even number of consecutive integers, we have:
M = (x − y + 1) + ... + x + (x + 1) + ... + (x + y) for some integers x and y, y>0.
So, M = (x + 1/2) * (2*y) = (2*a + 1)*b
Number of ways of solving these equations is equal to number of positive odd divisors of M.

Now, considering representation as sum of odd number of consecutive integers, we have:
M = (x − y) + ... + x + ... + (x + y) for some integers x and y, y>=0
So, M = x*(2*y + 1)

Now, let M = x+(x+1)+...+y = (1-x)+...(x-1) + x+(x+1)+...+y
Thus, for certain x and y, there are two ways of representation of M. One starting with positive integer 'x' and other starting with negative integer '1-x'.
Hence, only half of the representations of M start with a positive integer.

Number of ways of representing a number as sum of one consecutive integer is one i.e. the number itself.
Therefore, number of ways of representing M as two or more consecutive positive integers is one less than the number of positive odd divisors of M.

Code:

#include<stdio.h>
#define MAX 100
#define N 77

void sieve(int prime[])
{
	int i,j=0,k,temp[MAX]={0};
	for(i=2;i<MAX;i++)
	{
		if(temp[i]==0)
		{
			prime[j++]=i;
			for(k=2*i;k<MAX;k+=i)
			{
				temp[k]=1;
			}
		}
	}
}

int main()
{
	int i,prime[MAX];
	long long no_positive_odd_divisors=1;
	sieve(prime);
	i=1;
	while(prime[i]<=N)
	{
		int temp = prime[i];
		int quotient = N/temp;
		int sum=0;
		while(quotient!=0)
		{
			sum += quotient;
			temp *= prime[i];
			quotient = N/temp;
		}
		no_positive_odd_divisors *= sum+1;
		i++;
	}
	long long ways_of_representation = no_positive_odd_divisors - 1;
	printf("%lld\n",ways_of_representation);
}