Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #! /bin/bash
- AWK='
- BEGIN { stderr = "cat 1>&2"; }
- #.. Use binary search to find the largest b <= e, where b^3 < n.
- function bCbrt (n, e, Local, j, k, m) {
- j = 0; k = e;
- while (j < k) {
- m = int ((1 + j + k) / 2);
- if (m * m * m < n) j = m; else k = m - 1;
- }
- for (++j; j * j * j > n; j--) { }
- return ((j < e) ? j : e);
- }
- #.. Run the overall algorithm.
- function Ramanujan (nb, ne, Local, n, v,
- a, ab, ae, af, b, be, bf, c, d, de, tx, ty) {
- #.. Find the overall range for (a,b) pairs up to the limit.
- ab = 1; ae = af = bCbrt( ne / 2, ne); bf = 1 + bCbrt( ne, ne);
- printf ("nb = %s; ne = %s; ab = %s; af = %s; bf = %d\n",
- nb, ne, ab, af, bf) | stderr;
- #.. Try all the numbers in ascending order.
- for (n = nb; n <= ne; ++n) {
- be = bCbrt( n, bf);
- #.. Run a from low to high.
- for (a = ab; a <= ae; ++a) {
- #.. Run b from high to low, looking for an exact total.
- for (b = be; b >= a; --b) {
- v = a * a * a + b * b * b;
- if (v <= n) break;
- }
- #.. If v went low, it is a new lower limit for b.
- if (v < n || b < a) { be = b; continue; }
- #.. We have the first (a,b) for n, with small a and large b.
- tx = sprintf ("%16d %d,%d", n, a, b); ty = "";
- #.. Squeeze the interval (a+1,b-1) for others.
- be = de = b - 1;
- #.. Same logic to find any (c,d) intervals.
- for (c = 1 + a; c <= ae; ++c) {
- for (d = de; d >= c; --d) {
- v = c * c * c + d * d * d;
- if (v <= n) break;
- }
- #.. If v went low, it is a new lower limit for d.
- if (v < n || d < c) { de = d; continue; }
- #.. Found another (c,d) for same n.
- ty = sprintf ("%s; %d,%d", ty, c, d);
- #.. Shrink interval.
- de = d - 1;
- }
- #.. Print if more than one pair found.
- if (ty) print tx ty;
- #.. Avoid finding the (c,d) intervals again as (a,b).
- break;
- }
- }
- }
- { if ($1 <= $2) Ramanujan( $1, $2); else Ramanujan( $2, $1); }
- '
- echo "${1:-100000}" "${2:-1}" | awk -f <( printf '%s\n' "${AWK}" )
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement