Problem 5: Prime Function

Points:

Small Case: 10 Answer: 13

Large Case: 20 Answer: 467991

A function f:N->N is given by

f(1+sqrt(f(n)-1)) + 8f(n) = 9n^2 + 2n + 10*

where N is the set of natural numbers.

Given a positive integer m, the problem is to find the sum of all positive integers n such that f(n) is any prime number less than 'm'.

Small case: m=100

Large case: m=10000000

* a^b denotes a raised to the power of b

Solution:

f(1+sqrt(f(n)-1))+8f(n)=9n^2 + 2n + 10 ... 1

Let us consider the above equation for n=1
We get f(1+sqrt(f(1)-1)) + 8f(1) = 21.

Since f(n) is always a positive integer,Codomain being the natural numbers, f(1) can be either 0,1 or 2
If f(1)=0, we get sqrt(-1) on LHS of above equation,which is not possible as the domain for f(n) is the natural numbers and therefore f(1) isn't equal to 0 If f(1)=1,we get

f(1 + sqrt(1-1)) + 8 =21
=>f(1) + 8 =21
=>9 = 21

which is again a contradiction, hence f(1)isn't equal to 1

Thus f(1) = 2 .... 2

Substituting,Eqn. 2 in Eqn. 1,we get

f( 1 + sqrt(2-1)) + 16 = 21
=>f(2) = 5 .... 3

Similarly substituting Eqn 3 and subsequent equations in Eqn 1, we get
f(3) = 10
f(4) = 17
f(5) = 26

It can be seen that f(n) follows the pattern for n^2 + 1

The fact that f(n) is n^2 + 1, can be proved by mathmematical induction as
f(1) = 2
f(2) = 5
f(3) = 10

Lets assume that f(n) = n^2 + 1
Substituting above eqn. in Eqn. 1 we get,
f(1 + sqrt(n^2 + 1 -1) ) + 8(n^2 + 1) = 9n^2 + 2n + 10
=>f(1 + n) + 8n^2 + 8 = 9n^2 + 2n + 10
=>f(n + 1) = n^2 + 2n + 2
=>f(n + 1) = (n+1)^2 + 1

Hence proved.
After this the prime numbers upto m which are of the form n^2 + 1 are to found.
This can be easily done using the sieve method.

Code:

#include<stdio.h>
#include<math.h>

int arr[10000000];
int calculatePrimes(int n)
{
    int i=2;
    arr[0]=2;
    arr[1]=3;
    int k=1,j;
    int nextprime,flag=0,c=1;
    nextprime=5;
    int temp;
    int sum=1;
    while(nextprime<n)
    {
       flag=0;
       for(j=0;((j < i)&&(arr[j]<=sqrt((double)nextprime)));j++)
       {
           if(nextprime%arr[j] == 0)
           {
                          flag=1;
                          break;
           }
       }
       if(flag==0)
       {
                  
          arr[i]=nextprime;
          temp=(int)sqrt(nextprime-1);
          if((temp*temp + 1) == nextprime)
          {  
            sum+=temp;
          }
          i++;
       }
       if(c==-1)
                k++;
       nextprime=6*k +c;
       c=-c;
    }
    return(sum);
}

int main()
{
    int n;
    scanf("%d",&n);
    int sum=calculatePrimes(n);
    printf("%d\n",sum);
}