erdosstraus

165 days ago by lgstaub

n=5 
       

$\frac{4}{n}=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}$ where $a,b,c\in\mathbb{N}$ such that $1\leq a\leq b\leq c$.
$\frac{4}{3n}\leq\frac{1}{a}<\frac{4}{n}$, so $\frac{n}{4}<a\leq\frac{3n}{4}$
$\frac{\frac{4}{n}-\frac{1}{a}}{2}\leq\frac{1}{b}<\frac{4}{n}-\frac{1}{a}$, so $\frac{1}{\frac{4}{n}-\frac{1}{a}}<b\leq\frac{2}{\frac{4}{n}-\frac{1}{a}}$
$\Rightarrow na<(4a-n)b\leq 2na$

$\frac{1}{c}=\frac{4}{n}-\frac{1}{a}-\frac{1}{b}$, so $c=\frac{1}{\frac{4}{n}-\frac{1}{a}-\frac{1}{b}} \Rightarrow c=\frac{nab}{4ab-nb-na}$

def count_erdosstraus(n): count = 0 for a in range(floor(n/4)+1,floor(3*n/4)+1): if (4/n-1/a)!=0: for b in range(max(a,floor(1/(4/n-1/a))+1),floor(2/(4/n-1/a))+1): if (4/n-1/a-1/b)!=0: if 1/(4/n-1/a-1/b)>=b and 1/(4/n-1/a-1/b)==int(1/(4/n-1/a-1/b)): count += 1 #print('$\\frac{4}{'+str(n)+'}=\\frac{1}{'+str(a)+'}+\\frac{1}{'+str(b)+'}+\\frac{1}{'+str(1/(4/n-1/a-1/b))+'}$') return count 
       
import numpy as np def count_erdosstraus_fast(n): grid_a,grid_b = np.mgrid[floor(n/4)+1:floor(3*n/4)+1,floor(1/(4/n-1/(floor(3*n/4)+1)))+1:floor(2/(4/n-1/(floor(n/4)+1)))+1] print(grid_a.shape) invalid = ( (grid_a<=grid_b)*(n*grid_a < (4*grid_a-n)*grid_b)*((4*grid_a-n)*grid_b <= 2*n*grid_a) ).astype('int') #grid_c = invalid*np.nan_to_num(n*grid_a*grid_b/(4*grid_a*grid_b-n*(grid_a+grid_b))) grid_remainders = np.mod(n*grid_a*grid_b,4*grid_a*grid_b-n*(grid_a+grid_b)) invalid = invalid*((4*grid_a*grid_b-n*(grid_a+grid_b))>0) count = np.sum((invalid*(grid_remainders==0)).astype('int')) return count 
       
import numpy as np denom = 5 def count_erdosstraus_fast_by_row(n): a_bounds = [floor(n/denom)+1,floor(3*n/denom)+1] count = 0 for a in range(a_bounds[0],a_bounds[1]): b_bounds = [max(a,floor(1/(denom/n-1/a))+1),floor(2/(denom/n-1/a))+1] line_b = np.arange(b_bounds[0],b_bounds[1]) line_remainders = np.mod(n*a*line_b,denom*a*line_b-n*(a+line_b)) count += np.sum(line_remainders==0) return count 
       
points = [] oeis = [] for i in range(2,1500): if i%100==0: print(i) points.append([i,count_erdosstraus_fast_by_row(i)]) if points[len(points)-1][1] == 0: print(str(i)+': ' +str(points[len(points)-1][1])) list_plot(points) 
       
100
200
300
400
500
600
700
800
900
1000
1100
1200
1300
1400
100
200
300
400
500
600
700
800
900
1000
1100
1200
1300
1400
import colorsys lists_mod_k = [] k = 30 for i in range(0,k): lists_mod_k.append([]) for i in range(len(points)): if is_prime(points[i][0]): for j in range(1,k): if points[i][0]%k == j: lists_mod_k[j].append([points[i][0],points[i][1]]) #print(mod_four_is_one) print(lists_mod_k[2]) A = scatter_plot([], facecolor='black') B = scatter_plot([], facecolor='black') for i in range(1,k): rgb = colorsys.hsv_to_rgb(1/k*i, 1, 0.8) A = A+scatter_plot(lists_mod_k[i], facecolor=rgb, edgecolor=rgb) ''' for i in range(2,k,3): rgb = colorsys.hsv_to_rgb(1/k*i, 1, 0.8) B = B+scatter_plot(lists_mod_k[i], facecolor=rgb, edgecolor=rgb) ''' show(A) #show(B) 
       
[[2, 1]]
[[2, 1]]
#list_plot(mod_four_is_three, color='red')