CareerCup

x and y needs to be greater than n

as it is a homogeneous equation in relation to x and y. I just need to iterate up to the point that x==y



public static void main(String[] args) {
int nSol=0;
float n=2;
while(nSol<1000){
nSol=0;
n++;
for(float x=n+1;x<=2*n;x++){
float y=n*x/(x-n);
if(y==(int)y){
nSol++;
}
}
}
System.out.println("solucao "+n);
}

Notice that for n=4 we have (5-1)/20+1/20=5/(4x(4+1)), (3-1)/12+1/12=3/(4x(2+1)), and (2-1)/8 + 1/8 = 2/(4x(1+1)).

I.e. if 1/a+1/b=1/n, then the solution 1/(nk)+(k-1)/(nk)=1/(nk) works only if (k-1) divides n (since k-1 never divides k except for k=2).

So we can count n's divisors. If n has 5 divisors, then 1/a+1/b =1/n will have at least 5 solutions. For example, 4 has 3 divisors: 1, 2, and 4...

A number n with m distinct first-power prime divisors will have mC0+mC1+mC2+...+mCm = 2^m divisors in total.
So, since 2^10=1024, the number that is the product of the first 10 primes will definitely produce about a thousand solutions for 1/a+1/b=1/n.

Not sure if this number (6469693230) is the smallest n we desire, since one might be able to do better by repeating prime factors.

I am still running this script and it reached 110000 so far.

<?php

function findNumSolutions($n) {
  $num = 0;
  $prod = $n * $n;
  $diff = 0;
  $n2 = $n + $n;
  for ($i = $n + 1; $i <= $n2; $i++) {
    $prod += $n;
    $diff++;
    if ($prod % $diff == 0) {
      $num++;
    }
  }
  return $num;
}

$n = 1;
$maxSol = 0;

while (($num = findNumSolutions($n)) <= 1000) {
  if ($maxSol < $num) {
    $maxSol = $num; 
    print "\n";   
    var_dump([$n => $num]);
  }
  print "$n ";
  $n++;
}

print "\n";
var_dump([$n => $num]);

We can write equation as n = xy/(x+y). for any n, x > n.
1)Also since this is symmetric equation we just need to iterrate x upto the point where x == y.
2)Also we can see that for any positive integer n, (2n, 2n) will always be a solution.
so using (1) & (2) we now know that we need to iterate x from x+1 to 2n
now write equation in form of y = (n*x)/(x-n)
so for any give n,x we need positiive integer y which satisfies above condition.

def does_have_1000_sol(n):
	solution_cnt = 0
	for x in range(n+1, 2*n+1, 1):
		y =(n*x)/(x-n)
		if y % 1 == 0 :
			solution_cnt+=1
	if solution_cnt >= 1000:
		return True
	else:
		return False


if __name__ == "__main__":
	n = 1000
	flag = False
	while True:
		flag = does_have_1000_sol(n)
		if flag is True:
			print('n for which there are more than 1000 distinct solution is ',n)
			break
		n+=1

I got my answer n = 45 and the number of distinct solutions is 1029. There is my implementation.

public class FindLeastNWhichHasMoreThan1000Solutions {
	public static int getValidY(int n, int disp){
		double l = 0.1 ;
		double y = 0;
		while(l!=0){
			int x= n+disp;
			y = (n*x)/(x-n);
			l = y-(int)y;
		}
		return (int)y;
	}
	public static int countN(){
		int counter = 0;
		int n = 4;
		int disp = 1;
		while(true){
			int y = getValidY(n,disp);
			if(n+disp<=y){
				counter++;
				disp++;
			}else{
				if(counter<1000){
					n++;
					disp = 1;
				}else{
					return n;
				}
			}
		}
	}
	public static void main(String[] args) {
		int n = FindLeastNWhichHasMoreThan1000Solutions.countN();
		System.out.println(n);
	}
}

Found a bug on zhangboryan's solution; fixed and posted below. The answer is 141 and combination is 1004.

class Program
    {
        static void Main(string[] args)
        {
            int n = FindLeastNWhichHasMoreThan1000Solutions.countN();
		    Debug.WriteLine(n);

        }


        public class FindLeastNWhichHasMoreThan1000Solutions
        {
            public static bool getValidY(int n, int disp, out double y)
            {
                double l = 0.1;
                
                    int x = n + disp;
                    y = ((double)n * x) / (x - n);
                    l = y - (int)y;

                if (l != 0)
                    return false;

                return true;
            }

            public static int countN()
            {
                int counter = 0;
                int n = 4;
                int disp = 1;
                while (true)
                {
                    double y = 0;
                    if (getValidY(n, disp, out y))
                    {
                        counter++;
                    }

                    if (n + disp <= y)
                    {
                        disp++;
                    }
                    else
                    {
                        if (counter < 1000)
                        {
                            n++;
                            disp = 1;
                        }
                        else
                        {
                            return n;
                        }
                    }
                }
            }
        }

4,849,845