# Project Euler #130: Composites with prime repunit property

# Project Euler #130: Composites with prime repunit property

+ 1 comment shall i know what is the values of k,when i=703

+ 0 comments my entire code is right but i dont know why its failing i have checked taking more complex values can anyone help me out with this!

Scanner sc=new Scanner(System.in); long num=1; int j,val,k,c=0,r=0; int n1,n2; n1=sc.nextInt(); n2=sc.nextInt(); int arr[]=new int[50]; for(int i=4;i<22;i++) { j=i; num=1; c=0; while(j>1) { num=num+(long)(Math.pow(10, j-1)); j--;

}

k=5; while(k5;x--) { if(k%x==0 && (k-1)%i==0) { c++; break; }

} if(c>0) { arr[r]=k; r++; } } k++; } } Arrays.sort(arr);`for(int u=0;u<arr.length;u++) { if( u<arr.length-1 && arr[u]==arr[u+1] ) arr[u+1]=n2+1; if(arr[u]<n2 && arr[u]>n1) System.out.println(arr[u]); }`

+ 1 comment I'm wondering if someone solved this with Java (or any ather JVM language). I had a timeout on 7 test cases. After I reimplemented my solution in C using 128-bit integer I could complete.

+ 1 comment For those who passed all test cases, could you please give a hint on whether we should approach this problem by

Iterating on starting from to (

`+= 2`

and skipping multiples of ) and feed them to primality testing (e.g. Miller-Rabin), orGenerating all composite numbers from primes except and ? (e.g. using a heap)

Do we need to make use of the observation that is the least common multiple between and if ?

I was using the first approach and only passed the first 6 test cases. My implementataion of the

`A(i)`

function was by performing`curr = (curr * 10 + 1) % i`

on each iteration step, and the upper bound of this function is which is not very nice.**EDIT**: An observation, that for example , where is one of the valid answers, but , and are all invalid answers. I wonder if there is any pattern there. Also, it is curious that is the largest prime we need for up to .

+ 2 comments why 41 is not a part of answer ? It also satisfied all condition for 2 to 1000.

Sort 14 Discussions, By:

Please Login in order to post a comment