/* N,U,V,W,count are global */ /* We do a depth-first scan of the tree of possible tuple values. Starting with the first entry x, the entry at index i is given by U[i] * x + V[i]. At the leafs of the tree we check whether the equality U[n+1] * x + V[n+1] = x is solved by a positive integer. */ a354883(n) = { my(startTime); if (n < 3, return(0)); N = n; U = vector(N + 1); V = vector(N + 1); W = vector(N + 1); /* place minimum at index 3, i.e. start with x,x/2,x/4,3x/4+1 */ U[1] = 1; U[2] = 1/2; U[3] = 1/4; U[4] = 3/4; V[4] = 1; printf("n = %d:\n", n); startTime = getwalltime(); count = 0; recurse(4); printf("Found %d in %.1f seconds.\n", count, (getwalltime() - startTime) / 1000.0); return(count); }; recurse(i) = { my(u, v, x); u = U[i]; v = V[i]; if (i <= N, /* if 8u + v <= 2, then because of x >= 8 we have ux + v <= x/4, hence the current value is not larger than the assumed minimum, and we can abort */ if (8*u + v <= 2, return();); /* if u >= 2^k, k being the remaining number of steps, then (ux + v) / 2^k > x, hence not enough steps remain to descend to x, and we can abort as well */ if (u >= 2^(N + 1 - i), return();); i++; U[i] = u/2; V[i] = v/2 ; recurse(i); U[i] = 3*u; V[i] = 3*v + 1; recurse(i); return(); ); /* solve ux + v = x for x, x a positive integer */ if (u >= 1, return();); x = v / (1 - u); if (denominator(x) != 1, return();); for (i = 1, N + 1, W[i] = U[i] * x + V[i];); /* if the minimum is at index 3 and each entry is unique, then print with the minimum at the head */ if (W[3] == vecmin(W) && length(Set(W)) == N, for (i = 3, N, printf("%d,", W[i]);); printf("%d,%d\n", W[1], W[2]); count++; ); }; vector(30, n, a354883(n))