#Playing with numbers-6

Computer Science Level 3

Find the 6000 th ^\text{th} smallest positive integer such that it satisfy the property that it is coprime to the sum of their prime factors with repetition.

For example, 40 is one such number because 40 = 2 3 × 5 40 = 2^3 \times 5 and it is coprime to the sum of its prime factors with repetition:

gcd ⁡ ( 40 , 2 + 2 + 2 + 5 ) = 1. \gcd(40, 2 + 2 + 2 + 5) = 1.

For the previous problem : #Playing with numbers-5


The answer is 11212.

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
 
#include<stdio.h>
#include<math.h>

int coprime(unsigned long int x,unsigned long int y);
int G(unsigned long x);

int main()
{ unsigned long int result,i;
  result=0;i=1;
  while(result<6000)
  {result+=G(i);i+=1;}
  printf("%lu ",i-1);
}
//coprime returns 1 if x and y are coprime else 0
int coprime(unsigned long int x,unsigned long int y)
{ unsigned long int i;
  int r=1;
  for(i=2;i<=y;i++)
  {if(x%i==0 && y%i==0) {r=0;break;}
  }
  return r;
}
//G(x) returns 1 if x is coprime with the sum of its prime factors otherwise 0
int G(unsigned long x)
{unsigned long int i,n,result;
 n=x;
 i=2;result=0;
 while(n>1)
 {if(n%i==0)
  {result+=i;n/=i;i=2;}
  else i+=1 ;}
  if(coprime(x,result)==1)return 1;
  else return 0;
}


 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
 
def coprime(x,y):
    r=1
    for i in range(2,y+1):
        if(x%i==0 and y%i==0) :
            r=0
            break
    return r

def G(x):
    result=0
    n=x
    i=2
    while n>1:
        if n%i==0 :
            result+=i
            n/=i
            i=2
        else : i+=1
    if coprime(x,result)==1 : return 1
    else : return 0

result=0
i=1
while result<6000:
        result+=G(i)
        i+=1

print(i-1)

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Python 

 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
 
def gcd(a:int,b:int) -> int:
    return a if b==0 else gcd(b,a%b)

count = 1
n = 2

while True:
    t = n
    m = 0
    i = 2

    while t-1:
        if t%i==0:
            t//=i
            m+=i
        else:
            i+=1

    if gcd(n,m)==1:
        count+=1
        if count%100==0:
            print(count,n)
            if count==6000:
                exit()

    n+=1

Dev Sharma - 4 weeks, 1 day ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...