Is there a way in sagemath assisted by mathematics to find only and exclusively the first valid solution without calculating the other solutions? [closed]
Hi, I'm an aspiring amateur, I have found a way to bring the factorization of a number N into O ((log_2 (N)) ^ 2) in a system of this type:
var('N A y a B b C c D d w V v Z z U u')
eq0 = N-4899 == 0
eq1 = (-2 + sqrt(N + (1 - 2*y)^2))/4-A == 0
eq2 = 4*A+1-2*(y-1)-a == 0
eq3 = 8*(A-1)*a-(N-36)-(a-6)^2 == 0
eq4 = ((a-7)-2*(B-1))*((a-5)-2*(B-1))+1-(b-6)^2 == 0
eq5 = ((b-7)-2*(C-1))*((b-5)-2*(C-1))+1-(c-6)^2 == 0
eq6 = ((c-7)-2*(D-1))*((c-5)-2*(D-1))+1-(d-6)^2 == 0
eq7 = 8*(B-1)*a-(a-6)^2+36-(16*B*(B+1)+3) == 0
eq8 = 8*(C-1)*b-(b-6)^2+36-(16*C*(C+1)+3) == 0
eq9 = 8*(D-1)*c-(c-6)^2+36-(16*D*(D+1)+3) == 0
eq10= d-13 == 0
eq11= 8*(A-1)*(4*A+1)-(16*A*(A+1)+3-36)-(w-6)^2 == 0
eq12= ((w-7)-2*(V-1))*((w-5)-2*(V-1))+1-(v-6)^2 == 0
eq13= ((v-7)-2*(Z-1))*((v-5)-2*(Z-1))+1-(z-6)^2 == 0
eq14= ((z-7)-2*(U-1))*((z-5)-2*(U-1))+1-(u-6)^2 == 0
eq15= 8*(V-1)*w-(w-6)^2+36-(16*V*(V+1)+3) == 0
eq16= 8*(Z-1)*v-(v-6)^2+36-(16*Z*(Z+1)+3) == 0
eq17= 8*(U-1)*z-(z-6)^2+36-(16*U*(U+1)+3) == 0
eq18 = u-13 == 0
solutions = solve([eq0,eq1,eq2,eq3,eq4,eq5,eq6,eq7,eq8,eq9,eq10,eq11,eq12,eq13,eq14,eq15,eq16,eq17,eq18],N,A,y,a,B,b,C,c,D,d,w,V,v,Z,z,U,u)
sol = solutions
print(sol)
As can be seen from the outputs, a factorizes N, and every solution is good.
[
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == -25, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == -3, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == -25, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == -25, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == -7, D == 5, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == -25, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == 37, c == -9, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == -3, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == 37, c == -9, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == -15, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == -15, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == 17, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == -3, V == 17, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == -9],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == -15, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == -15, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == -57, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == 17, Z == -7, a == 69, b == 37, c == 21, d == 13, u == 13, v == -25, w == 69, y == 1, z == 21],
[A == 17, B == 17, C == 9, D == 5, N == 4899, U == 5, V == 17, Z == 9, a == 69, b == 37, c == 21, d == 13, u == 13, v == 37, w == 69, y == 1, z == 21]
]
What I would like to ask is there a way in sagemath assisted by mathematics to find only and exclusively the first valid solution without calculating the other solutions?
If you do not know what
solvedoes, you also won't know the time complexity of your algorithm...Strictly speaking, there is no "first" solution (in general, there is no "natural" ordering of the roots of a given system of equations). What you seem to want is to avoid the bother of computing all solutions, since any of them is sufficient for your needs.
It happens that, notwithstanding the case of "obvious" solution(s), most of the work needed to obtain one solution is also needed to obtain the other solutions. Let $t$ the time necessary to get the $n$ solutions to a given system ; the time necessary to get one solution among $n$ is therefore not $\frac{t}{n}$ but much closer to $t$...
@Emmanuel Charpentier@FabianG thanks, i get it. forgive my ignorance. What is the computational complexity as a function of the number of unknown variables in this type of system?
Please reopen