#Playing with numbers-5

Computer Science Level pending

A function F ( x ) F(x) finds the number of ways a number x x can be expressed as the sum of 2 mutually coprime numbers. If ∑ i = 2 m F ( i ) = 18054 \sum_{i=2}^{m}F(i)=18054 ,such that i i is a prime number, find m m .

Click here for the previous problem of this series.


The answer is 659.

Rafsan Rcc by Rafsan Rcc , 17, Bangladesh

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

Rafsan Rcc
May 12, 2021 
 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include<stdio.h>
#include<conio.h>

int prime(unsigned long int x);
int coprime(unsigned long int x,unsigned long int y);
unsigned long int F(unsigned long int x);

int main()
{   unsigned long int i,result;
    result=0;
    while(result<18054)
    {if(prime(i)==1){result+=F(i);};
    i+=1;}
    printf("m=%lu",i-1);
}
//prime returns 1 if x is prime otherwise 0
int prime(unsigned long int x)
{   unsigned long int i;
    int r=1;
    for(i=2;i<=x/2;i++)
    {if(x%i==0){r=0;break;}
    }
    return r;

}
//coprime returns 1 if x and y are coprime otherwise 0
int coprime(unsigned long int x,unsigned long int y)
{   unsigned long int i; 
    int r=1;
    for(i=2;i<=x;i++)
    {if(x%i==0 && y%i==0)
    {r=0;break;}}
    return r;
}

unsigned long int F(unsigned long int x)
{   unsigned long int result,i;
    result=0;
    for(i=1;i<x/2+1;i++)
    {if(coprime(i,x-i)==1) result+=1;}
    return result;
}


 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
27
28
29
30
31
32
 
#returns True if x is a prime otherwise False
def prime(x):
    r=True
    for i in range(2,x//2+1):
        if x%i==0 :
            r=False
            break
    return r
#coprime returns True if x and y are coprime otherwise False
def coprime(x,y):
    r=True
    for i in range(2,x+1):
        if (x%i==0 and y%i==0):
            r=False
            break
    return r

def F(x):
    r=0
    i=1
    while i<x/2+1:
        if coprime(i,x-i):r+=1
        i+=1
    return r

result=0
i=2
while result<18054:
    if prime(i) : result+=F(i)
    i+=1

print(i-1)

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Why does your F(4) evaluates to 1? Shouldn't it be 2?

Pi Han Goh - 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...