The thread’s moved on, but I wanted to say: Yeah, that’s neat.
This is, effectively, the same solution as septimus gives (in the D language):
import std.stdio;
template NickelNDime(uint target) {
void result(ref ulong total, uint currentValue = 0) {
uint testValue = currentValue + 1;
if (testValue == target) ++total;
else if (testValue < target) {
result(total, testValue);
testValue = currentValue + 5;
if (testValue == target) ++total;
else if (testValue < target) {
result(total, testValue);
testValue = currentValue + 10;
if (testValue == target) ++total;
else if (testValue < target) result(total, testValue);
}
}
}
}
int main(string[] args) {
ulong total = 0;
NickelNDime!(100).result(total);
writefln("Result: %s", total);
return 0;
}
I gave up waiting for it to complete, but do get the correct answer for 25. I’d be interested in optimizing it – directly stacking instead of using the function stack, and splitting it into threads – but left it as is for the sake of keeping the code clear.
The task I would give, should anyone want to try it:
You are given a bundle of nodes. Each node has a list of nodes that it is connected to and a cost to travel to that node. There are no orphaned nodes, but any one node is only connected to a subset of all nodes. Create a method that accepts two nodes, an origin and a destination, and returns the cheapest path.
struct Node {
Node others[]; // guaranteed to be the same length as cost[]
uint cost[]; // guaranteed to be the same length as others[]
// any variables you want to add
}
Node[] cheapestPath(Node origin, Node destination);
Just to nitpick: Costs must be stipulated to be non-negative, as otherwise winning strategy is to find a loop of negative cost and spin around it for a while! 
They are an unsigned int in my example, and should be presumed to be a minimum of 1.
It’s a straight forward linear recurrence so you should be able to compute it in under a second using memoization or something similar.
Yeah, the problem with Sage Rat’s code, from an efficiency standpoint, is just the lack of memoization.
Anyway, I tackled the cheapest path problem, straightforwardly using Dijkstra’s algorithm:
data Distance a = Finite a | Infinite
distComp (Finite a) (Finite b) = compare a b
distComp (Finite _) Infinite = LT
distComp Infinite (Finite _) = GT
distComp Infinite Infinite = EQ
distAdd (Finite a) (Finite b) = Finite (a + b)
distAdd _ _ = Infinite
dijkstra nodes node_eq metric source dest
= reverse $ fst $ dijkstra_helper source (node_eq source)
(
-> if node_eq source n then ([], Finite 0) else ([n], metric source n))
where dijkstra_helper current visited path = if visited dest then path dest
else let (pcurr, dcurr) = path current
path' = memo $
-> minimumBy (\(_, d1) (_, d2) -> distComp d1 d2)
[path n, (n:pcurr, distAdd (metric current n) dcurr)]
dist' = snd . path'
current' = minimumBy (\a b -> distComp (dist' a) (dist' b))
(filter (not . visited) nodes)
visited' n = node_eq current' n || visited n
in dijkstra_helper current' visited' path'
memo f = let l = [(n, f n) | n <- nodes]
in
-> head [fn | (n', fn) <- l, node_eq n n']
dijkstra_marshall nodes node_eq node_neighbors source dest
= dijkstra nodes node_eq metric source dest
where metric n1 n2 = if node_eq n1 n2 then Finite 0
else case [d | (n2', d) <- node_neighbors n1, node_eq n2 n2'] of
(d:_) -> Finite d; [] -> Infinite
dijkstra does all the work; its arguments are a list of nodes, a function comparing nodes for equality, a function taking in two nodes and returning the distance from the first to the second (possibly infinite), a source node, and a destination node; it returns the shortest path from the source to the destination (specified as a list of nodes in order, not including the source but including the destination).
dijkstra_marshall is a wrapper for dijkstra where the argument giving the distance between two nodes is replaced with a function sending any node to a list of pairs of its neighbor nodes and the distances to them
For verification of correctness, here’s an undirected graph example (taken from the graphic on Wikipedia’s article for Dijkstra’s algorithm):
nodes = [0..5]
node_eq = (==)
neigh 0 = [(1, 9), (3, 6)]
neigh 1 = [(0, 9), (2, 2), (4, 14)]
neigh 2 = [(1, 2), (3, 11), (4, 9), (5, 10)]
neigh 3 = [(0, 6), (2, 11), (5, 15)]
neigh 4 = [(1, 14), (2, 9), (5, 7)]
neigh 5 = [(2, 10), (3, 15), (4, 7)]
shortestPaths = [(a, b, dijkstra_marshall nodes node_eq neigh a b) | a <- nodes, b <- nodes]
[Of course, actually computing shortestPaths this way would be wasteful, since it restarts Dijkstra’s algorithm from scratch each time the destination node is changed even if the source node remains the same… It’s just a correctness test of the single-use code above]
Anyway, shortestPaths evaluates to [(0,0,),(0,1,[1]),(0,2,[1,2]),(0,3,[3]),(0,4,[1,2,4]),(0,5,[3,5]),(1,0,[0]),(1,1,),(1,2,[2]),(1,3,[2,3]),(1,4,[2,4]),(1,5,[2,5]),(2,0,[1,0]),(2,1,[1]),(2,2,),(2,3,[3]),(2,4,[4]),(2,5,[5]),(3,0,[0]),(3,1,[2,1]),(3,2,[2]),(3,3,),(3,4,[2,4]),(3,5,[5]),(4,0,[2,1,0]),(4,1,[2,1]),(4,2,[2]),(4,3,[2,3]),(4,4,),(4,5,[5]),(5,0,[2,1,0]),(5,1,[2,1]),(5,2,[2]),(5,3,[3]),(5,4,[4]),(5,5,)], which seems to me correct.
And here’s a directed graph example (taken from this random graphic I found on the web):
nodes = [1..10]
node_eq = (==)
neigh 1 = [(2, 10), (4, 20), (5, 20), (6, 5), (7, 15)]
neigh 2 = [(3, 5), (4, 10)]
neigh 3 = [(2, 15), (4, 5)]
neigh 4 = [(5, 10)]
neigh 5 = [(6, 5)]
neigh 6 = []
neigh 7 = [(6, 10)]
neigh 8 = [(1, 5), (2, 20), (7, 5)]
neigh 9 = [(2, 15), (8, 20), (10, 10)]
neigh 10 = [(2, 5), (3, 15)]
shortestPaths = [(a, b, dijkstra_marshall nodes node_eq neigh a b) | a <- nodes, b <- nodes]
shortestPaths evaluates to [(1,1,),(1,2,[2]),(1,3,[2,3]),(1,4,[4]),(1,5,[5]),(1,6,[6]),(1,7,[7]),(1,8,[8]),(1,9,[9]),(1,10,[10]),(2,1,[1]),(2,2,),(2,3,[3]),(2,4,[4]),(2,5,[4,5]),(2,6,[4,5,6]),(2,7,[7]),(2,8,[8]),(2,9,[9]),(2,10,[10]),(3,1,[1]),(3,2,[2]),(3,3,),(3,4,[4]),(3,5,[4,5]),(3,6,[4,5,6]),(3,7,[7]),(3,8,[8]),(3,9,[9]),(3,10,[10]),(4,1,[1]),(4,2,[2]),(4,3,[3]),(4,4,),(4,5,[5]),(4,6,[5,6]),(4,7,[7]),(4,8,[8]),(4,9,[9]),(4,10,[10]),(5,1,[1]),(5,2,[2]),(5,3,[3]),(5,4,[4]),(5,5,),(5,6,[6]),(5,7,[7]),(5,8,[8]),(5,9,[9]),(5,10,[10]),(6,1,[1]),(6,2,[2]),(6,3,[3]),(6,4,[4]),(6,5,[5]),(6,6,),(6,7,[7]),(6,8,[8]),(6,9,[9]),(6,10,[10]),(7,1,[1]),(7,2,[2]),(7,3,[3]),(7,4,[4]),(7,5,[5]),(7,6,[6]),(7,7,),(7,8,[8]),(7,9,[9]),(7,10,[10]),(8,1,[1]),(8,2,[1,2]),(8,3,[1,2,3]),(8,4,[1,4]),(8,5,[1,5]),(8,6,[1,6]),(8,7,[7]),(8,8,),(8,9,[9]),(8,10,[10]),(9,1,[8,1]),(9,2,[2]),(9,3,[2,3]),(9,4,[2,4]),(9,5,[2,4,5]),(9,6,[8,1,6]),(9,7,[8,7]),(9,8,[8]),(9,9,),(9,10,[10]),(10,1,[1]),(10,2,[2]),(10,3,[2,3]),(10,4,[2,4]),(10,5,[2,4,5]),(10,6,[2,4,5,6]),(10,7,[7]),(10,8,[8]),(10,9,[9]),(10,10,)]. If you spot an error in there, let me know. (Probably not the best graph to test on, but I’m lazy…)
Also, for pedantry’s sake, I said above “(specified as a list of nodes in order, not including the source but including the destination)”, but should actually have noted that the destination is only included if it is distinct from the source (i.e., what is output is the ordered list of nodes which are traversed after the source)…
Ah, I thought septimus was partially controlling his own stack, but I think I have an inkling of what he’s actually doing. I’ll have to study it when I’m more awake to be able to internalize it.
It occurs to me I had no good reason for this insertion of 0-length self-loops at every node…
Oh well, one wasted line.
I was going to tackle the path problem but there’s no point now. But my solution is kind of neat, so I’ll sketch it out.
Given n nodes create an n x n matrix, A, where the entry in i, j is x^w where w is the weight of the edge between nodes i and j. Enter 0 in the i, j spot if nodes i and j are not connected. Compute M = A + A^2 + … + A^(n-1). The entry in the i, j spot of M is a polynomial and the exponent of its lowest degree term is the minimum weight of a path between nodes i and j.
This is not as efficient as Djikstra, but we have calculated a lot more, including the min weight path between any pair of nodes, and the number of distinct paths that have that weight.
But the one thing you haven’t calculated is an actual path between the nodes… 
Also, note, as you presumably realize, that you calculate a lot more than just the information about the minimum weight paths. What you calculate is, for, each weight, the number of paths of edge-number between 0 and n, exclusive, of that weight.
But I insist what you ought to calculate is M = 1 + A + A^2 + A^3 + …, with starting term A^0 and continuing ad infinitum. (Equivalently, in some sense worth thinking more about, M = (1 - A)^{-1}). Then you get the same thing with no edge-number restrictions on the path.
Returning to the change-making problem for a moment, changing “int” to “long long” (and fixing one typo), the code I posted gets Lance’s answer of 8437020668201 ways to make change of a dollar. (With the “memo” its run is essentially instantaneous; without “memo” my laptop spends two minutes just solving for $0.71.)
But even “long long” isn’t enough to make change for a paltry $1.50. (Even the stingiest Doper will say “just keep the change” before the waitress finishes enumerating those options.)
So, just to prove “we don’t need no steenking bignum packages,” here’s a self-contained program to show that the number of ways to change $75.22 is less than googol^10.
char Nways[9000][1200];
void addin(char *d, char *s)
{
int sc, dc, carry = 0;
while ((sc = *s++) || *d) {
dc = (*d ? *d : *d + '0') + (sc ? sc - '0' : sc) + carry;
carry = dc > '9' ? (dc -= 10, 1) : 0;
*d++ = dc;
}
if (carry) *d = '1';
}
main()
{
int i, j;
Nways[0][0] = '1';
for (j = 1; j < 9000; j++) {
Nways[j][0] = '0';
if (j >= 1) addin(Nways[j], Nways[j-1]);
if (j >= 5) addin(Nways[j], Nways[j-5]);
if (j >= 10) addin(Nways[j], Nways[j-10]);
printf("There are ");
for (i = strlen(Nways[j]) - 1; i >= 0; i--)
printf("%c", Nways[j]*);
printf(" ways to make change of $%d.%02d
", j/100, j%100);
}
}
Sorry for not responding earlier; I think I must have misremembered how to do this algorithm and can’t quite get it right now. I think all that’s required is just an axis that cuts the polygon (for a quadrilateral, any two alternate points). So you’d need to rotate it. Possibly there’s a way to incorporate the rotation with the sign test, but I’m not sure about that.
Ah, I think I see what you’re getting at. You rotate your polygon so the axis is horizontal, and then if it’s convex, the vertical component of each point must cross zero only at the two vertices that define the axis. The catch is that you have to try every pair of points as a possible axis. And I think it depends on already having an ordering of the points, too. With only four points, it’d be doable to go through exhaustively, but much more than that, and the method would quickly become unworkable.
Eh, in thinking about it some more, I think this is a better, more straightforward presentation of the calculation (in case anyone is still interested):
Our goal is to calculate the sum of 1/n[sup]2[/sup] over all nonzero integers n. To get a better grip on this sum, we’ll calculate it as f(0), where f(x) is the sum of e[sup]nx[/sup]/n[sup]2[/sup] over all nonzero integers n.
What is the value of introducing this f? Well, we can see quite readily that its second derivative f’‘(x) is the sum of e[sup]nx[/sup] over all nonzero integers n, whose behavior is quite tractable: adding 1 to this and then multiplying by e[sup]x[/sup] - 1 yields 0, so we can conclude that f’‘(x) is constantly -1 (at least, where e[sup]x[/sup] - 1 is invertible). [If you are attentive to such things, you may feel that I am handwaving in the following right over the issue of what happens at the singularities; we should perhaps fully establish that f’’ + 1 is the appropriate Dirac comb]. We can now recover f by double-integrating.
Integrating once, we find that f’(x) = the sum of e[sup]nx[/sup]/n over nonzero n = -x + f’(0). To discover the value of f’(0), we take the average value of both sides of the equation as x runs from 0 to 2ln(K), where K is one half revolution. This causes each e[sup]nx[/sup] to spin uniformly through 2n half revolutions (or n complete revolutions), and thus by symmetry to have an average value of zero. Accordingly, the left hand side of our equation for f’(x) will have an average value of zero; the right hand side’s average value is -ln(K) + f’(0), establishing that f’(0) = ln(K), so that f’(x) = -x + ln(K).
Integrating once more, we find that f(x) = sum of e[sup]nx[/sup]/n[sup]2[/sup] over nonzero n = -x[sup]2[/sup]/2 + ln(K)x + f(0). By the same average value trick, the left hand side goes to zero again, while the right hand side has average value -2ln(K)[sup]2[/sup]/3 + ln(K)[sup]2[/sup] + f(0); thus, f(0) = -ln(K)[sup]2[/sup]/3.
Of course, rather famously, albeit essentially by definition, |ln(K)| = π; thus, we can conclude that our magic number = π[sup]2[/sup]/3.
I created a memoized version of my code. The ulong appears to run out of bits after $1.47. I can, however, iterate all results from $0.01 to $1.47 in an instant with the memoizer.
Oddly enough, I discovered that D has a memoize template as part of their standard library, so I wouldn’t have needed to write it myself.
Here’s the updated version (not using the memoize template):
import std.stdio;
template NickelNDime(uint target) {
static ulong[target + 1] memo;
void init() {
for (int i = 0; i < (target + 1); i++) memo* = ulong.max;
}
void result(ref ulong total, uint currentValue = 0) {
if (memo[currentValue] != ulong.max) {
total += memo[currentValue];
return;
}
ulong before = total;
uint testValue = currentValue + 1;
if (testValue == target) ++total;
else if (testValue < target) {
result!(target)(total, testValue);
testValue = currentValue + 5;
if (testValue == target) ++total;
else if (testValue < target) {
result!(target)(total, testValue);
testValue = currentValue + 10;
if (testValue == target) ++total;
else if (testValue < target) result!(target)(total, testValue);
}
}
memo[currentValue] = total - before;
}
}
void xtimes(int N : 1)(ref ulong total) {
NickelNDime!(N).init();
NickelNDime!(N).result(total);
writefln("Result: %s -> %s", N, total);
}
void xtimes(int N)(ref ulong total) {
NickelNDime!(N).init();
NickelNDime!(N).result(total);
writefln("Result: %s -> %s", N, total);
total = 0;
xtimes!(N - 1)(total);
}
int main(string[] args) {
ulong total = 0;
xtimes!(147)(total);
return 0;
}
The output:
Result: 147 -> 14808717293036192482
Result: 146 -> 10905846801866117440
Result: 145 -> 8031586538673604586
Result: 144 -> 5914843982327456720
Result: 143 -> 4355973650637328062
Result: 142 -> 3207947073792568901
Result: 141 -> 2362485463324282656
Result: 140 -> 1739847147110172123
Result: 139 -> 1281306548675186892
Result: 138 -> 943615348282072821
Result: 137 -> 694923417377506141
Result: 136 -> 511774799868230198
Result: 135 -> 376895409235975743
Result: 134 -> 277563783014941766
Result: 133 -> 204411228562686340
Result: 132 -> 150538193090780104
Result: 131 -> 110863516345880335
Result: 130 -> 81645189199009488
Result: 129 -> 60127417378172305
Result: 128 -> 44280702341880340
Result: 127 -> 32610424418495839
Result: 126 -> 24015874286374120
Result: 125 -> 17686437022024489
Result: 124 -> 13025137074083121
Result: 123 -> 9592333130025896
Result: 122 -> 7064252326403930
Result: 121 -> 5202452860496727
Result: 120 -> 3831334798812694
Result: 119 -> 2821577962208844
Result: 118 -> 2077944793358605
Result: 117 -> 1530297805717789
Result: 116 -> 1126984403852904
Result: 115 -> 829965149128674
Result: 114 -> 611225981848381
Result: 113 -> 450136010263361
Result: 112 -> 331501660189414
Result: 111 -> 244133657831129
Result: 110 -> 179791687475176
Result: 109 -> 132407187001858
Result: 108 -> 97510977377455
Result: 107 -> 71811741675471
Result: 106 -> 52885596893101
Result: 105 -> 38947479805117
Result: 104 -> 28682784583162
Result: 103 -> 21123372696492
Result: 102 -> 15556260682814
Result: 101 -> 11456373462852
Result: 100 -> 8437020668201
Result: 99 -> 6213425041241
Result: 98 -> 4575863005492
Result: 97 -> 3369884099556
Result: 96 -> 2481743625132
Result: 95 -> 1827674553754
Result: 94 -> 1345986845429
Result: 93 -> 991249008186
Result: 92 -> 730003120406
Result: 91 -> 537609169519
Result: 90 -> 395921073206
Result: 89 -> 291575190320
Result: 88 -> 214729897750
Result: 87 -> 158137354018
Result: 86 -> 116459901859
Result: 85 -> 85766635119
Result: 84 -> 63162646923
Result: 83 -> 46515990030
Result: 82 -> 34256596869
Result: 81 -> 25228194454
Result: 80 -> 18579247767
Result: 79 -> 13682645647
Result: 78 -> 10076553702
Result: 77 -> 7420855290
Result: 76 -> 5465072286
Result: 75 -> 4024740429
Result: 74 -> 2964011246
Result: 73 -> 2182839459
Result: 72 -> 1607547125
Result: 71 -> 1183874401
Result: 70 -> 871861691
Result: 69 -> 642080699
Result: 68 -> 472858953
Result: 67 -> 348235879
Result: 66 -> 256457456
Result: 65 -> 188867492
Result: 64 -> 139091088
Result: 63 -> 102433381
Result: 62 -> 75436845
Result: 61 -> 55555254
Result: 60 -> 40913500
Result: 59 -> 30130658
Result: 58 -> 22189693
Result: 57 -> 16341578
Result: 56 -> 12034710
Result: 55 -> 8862904
Result: 54 -> 6527049
Result: 53 -> 4806843
Result: 52 -> 3540013
Result: 51 -> 2607044
Result: 50 -> 1919938
Result: 49 -> 1413916
Result: 48 -> 1041272
Result: 47 -> 766855
Result: 46 -> 564762
Result: 45 -> 415917
Result: 44 -> 306290
Result: 43 -> 225558
Result: 42 -> 166114
Result: 41 -> 122344
Result: 40 -> 90105
Result: 39 -> 66354
Result: 38 -> 48859
Result: 37 -> 35979
Result: 36 -> 26501
Result: 35 -> 19522
Result: 34 -> 14378
Result: 33 -> 10585
Result: 32 -> 7791
Result: 31 -> 5738
Result: 30 -> 4229
Result: 29 -> 3117
Result: 28 -> 2295
Result: 27 -> 1687
Result: 26 -> 1241
Result: 25 -> 915
Result: 24 -> 676
Result: 23 -> 499
Result: 22 -> 366
Result: 21 -> 268
Result: 20 -> 197
Result: 19 -> 146
Result: 18 -> 109
Result: 17 -> 80
Result: 16 -> 58
Result: 15 -> 42
Result: 14 -> 31
Result: 13 -> 24
Result: 12 -> 18
Result: 11 -> 13
Result: 10 -> 9
Result: 9 -> 6
Result: 8 -> 5
Result: 7 -> 4
Result: 6 -> 3
Result: 5 -> 2
Result: 4 -> 1
Result: 3 -> 1
Result: 2 -> 1
Result: 1 -> 1
Haskell code for the penny-nickel-dime thing:
numWays = let memo = 1:[sum [numWays (n - x) | x <- [1, 5, 10]] | n <- [1..]]
in (
-> case compare n 0 of LT -> 0; EQ -> 1; GT -> memo !! n)
For example, numWays 7522 (the number of ways to make $75.22) returns
996857165439680621133609511643623033006131663020526242857629599571333964243488965310933626339398893662875905261667555279824437190487568377168522706397979278299834335655333463132185462876734351753410484021536570468012018485224661120009452023346833043261397944175737782127416317781564083219517816458800931610401407799753770150554177597496744069401350873353517050277881631981244227123481141676458717680230826966446813037840173691683365918785500656796424863307765169283629054718953289585602850193613710964319115862379488773213968818923246523184026160738017633700828496879978210049455936124670877619621056231605858525742908426356186879515998644529056731007747682836502654178477620261434565030122154571017881247061449546900165438081094564843547330016085780073849857154396638852477987177262313058089593336759890712488165588312874935491907001413083113256276532656876625155717994131920052210232099821027287359287798444061428580796776068011259579582155808321073549093359449477166728628879566251635246987579876
, which is 999 digits, as septimus pointed out
Actually, I double-covered the n = 0 case for no reason. Instead, let me minorly modify that to
numWays = let memo = 1:[sum [numWays (n - x) | x <- [1, 5, 10]] | n <- [1..]]
in
-> if n < 0 then 0 else memo !! n
In case anyone was wondering, with the use of bignums and memoization:
in r5rs
(define numways-usage
(lambda (target cur memo)
(if (> cur target)
0
(if (= cur target)
1
(if (zero? (vector-ref memo cur))
(begin
(vector-set! memo cur
(+
(numways-usage target (+ cur 1) memo)
(numways-usage target (+ cur 5) memo)
(numways-usage target (+ cur 10) memo)
)
)
(vector-ref memo cur)
)
(vector-ref memo cur)
)
)
)
)
)
(define numways (lambda (target) (numways-usage target 0 (make-vector target 0))))
(numways 100000)
produces this beaut of a number (13286 digits long):
27883031537599265292098197969818777995298042318083317517189511790785412042170485925186927162947113315931488502750909672417310963706655195712799455644515479690747058263695658120101469022822273768427084667846401940846165819307974859987899364731112614008149042640604622453646289659246092369735585093411072511169643794521819413211255319524157496176171186077799103156753411278237419430044787933498782689102348610043109559630140599855215460132052164296772735535824071163466837678251432054975289175092822839047747084528415485365664964152226339374476701838647439597409023432346260545132689827784017131511295426222831510164947700899966090983380931050118997931519769340872666108598700022611737152347396559106304910366305843550566958311800812118380649196039023930951873312355377457637380925864819444603516670808019112386505529025709105430254443433336523271768639825775765019940314843897528267524004137675424041796269874779579102549071582598650769500754191283607727011586269295650806237214021432427501799848153356626392797950525004285358121445343596352198301640945102816910884712160976307346289738850676756867119770255274684381065381610369798154248213353000897945888794457502383745908774116297219883229444435562241577600261605107486711007636956057362289505254108370354744973568822067968480429678133053941618637001790425236791583971501646199444777455738955983023943749313657870823574840413003176293206481691879596681769290259924636737596720151096261462179103142580811877675712217826613598649098775938189854653904033624390793679707601079123808883968670121731369698177112430173296902470297391395800262762703002803243299293688405171470651966507489186120043305699571780030417254405159774293602928023317716232171079150846596002953573841069707050549147118286341871119061597975789434116908952317261022196615925504360896784666366824127990441786522812109115988500632115846427677911882512146940122440988231923564187599465789529815347439500384693444245297481147483994607972284185201840294783801270147614984935294089378243475263221999344899858358993374624432104406519919141370035551506083314380028290710519622198115919931444805448186707382807925742356826234899596125907592786740133761080011091541928196592440876356946417968814273717531982809982716214121598098737105359399743701281717123243592460153030334024733597589920096742159099396826529442044952984668581171505176876981059284472934361384483432192974696786541311974514510448034484134187341298146113118188806777723758362532231172032731407678575298553856166855338209084258475340613580635030304787548499152065960282484025508015292276422491973048300769651092708750199080316975397152921064329056852492826356409999741166600595574698398468719929942049541799115791667625632334096196905330519078187842894115995717236554250617464848667249586316553043280003118060304804281526401724529312349812269769530796187712019155627362782062370010424707118101679641654005030161325238869185720196791041824785924572727093824846952774051391477007652850017589693117958253690306527247236749320002616001490596179740903096479137308867448678920411927594831143342488843349553874939221669272074535677442996602532063449025407626675164065108217227224077271521591902494761392115634146343384342344148949755822305191620906886148555201964986986409528756842380682626821888612791443805819937190612038947117899299198138442167366542109825664334067731888040248101346411048879774353712459933831993494969456980252152734786598192422588498347259494748883038035702046639081908030950818913028842413258225704893228497810955518712305310804032818970275127087557373151720100996299469730576542200657340209171001559421832204727091629856828242589043496287211168055404056904463930772198490088107650111946372019766586431796398982475517380430040016229832009044469833699993485504620617002180716350645440749424812156392839815842066630404763122821562229840970519092872757852598194369047767891832361196264148537363610329811956587603787899055205285986103136044427224683268201147650520741781108366429264958404525944681403718330748876453698295455609987205479157161005313768153843789184375481978570254709934713377187576968902326270224985008415574620872245803415385417461533716701136374124616623770865095651136863336172651482958158171342669572688082215475067298289328653513010296609566493563318243415919823611211785583648595953264336246232947802104091409975836771844252887374851678073361330189177277421270415080384483583316221325504311429022046417979782521094323732594175934979007021471146635934192019098149063988709378797544252883771645193847574607192987041163315857382722675492573963244504836231410705659065204601035787025088492454897308782544515883917373238817669071193290346014604318396533557105292446402759857323551219097313750679777550628363829436964403907776160389563698957345914109614203205130275802482980338164526014085505802334439945885160411280082286002898252047470186348777744255278932378340924899353001194765239609260506784956366629899157603090719397743545925076247837331210063330740060997541990333906873013025586979861703055841031412310120391816781894309610150186364450959556611237438674119843296287432815590916323187539183953981923590452870244369689410142801259778402499908620473778840366381369902918349282795857054196242116858650843503523427714054836630834747459360334578159201284696388193816764433384086874907608487577243849195428802556058900283114482881250024394469061078910765355357285656595385922276363846914347081719152861381458518262280531072390506321272870318290280708457503990055893373289041284745498758137812374264276362802980430223440358784634510917841325922478384332993982452452666965355013808894418355713681189477447364462848605538154956655333384877514261317022280480797327245986113460915680502355543598621353660003436371557008927947063825483843840701292217522377770348631202389035911541820032438658013431239563589841575383151248349664903530523247837463997496832140145439574914445602486039206177928650918487600014533960066536354495293295939026300942650435788329380016587235981768521815598689583910638043997335639826285317579661483734003423505743017115641027409091322303915442569496444369556108562722778442634957975845611251771470917624389268820989740801781399290704172344738190169985519817323189995920964088865095611376743264388957149553836643347857771569263494427404406565768854733080324480605998346446843060049324389554871969458423977788713201229638419206391489812376679718591212922507285927609993056738088449917092650497383866258904487615227300693077576863473216637079963338359109224133516911248056522994704699272209906957434985282039542114046848842451212115234201571817415372722904820334804545886212204646199264004379656627578713602539191415143467575881229041280021985347823799579914402290572127539426664720043034072759359758243184995735697290607021324129654212511438090556123778993281099691934325269683664556331301496329512742956140040534411578418241997623654025975292880424874625278792493348931458163775922727517210363953249573285522780932922248944725274392592537230998010893087932067981457173639693216792264060917933580191117100317903247497680279331556864076148973530637349384656541389206359252532721325678531448347836868127961404435302789734338288700348207617900864350646563116266819648735172494959193018040976173427580807323769776479713979078927494874702615308691244172851545554008115713514253270967708745570823020609243423289140421018927633712558987461693154619706423224550325382011793431598428244380795625088456863861325337416136757040958096479293115590881999849353534711367299656091603552532535907286994745604400749338533407934077530198240046314875869946487767895722698230300171277265701885463138542930323406889820774794409109652891220992174070557618114600246932874196472652134859995825792435202419247999997110274717853805688221197040091050142525478956377029440411403358739217459847197978224178344422168364050744229833649005920999077397077366889991701002270195780527096244952958943991342829332628624931473768443013254224687840939184695718846176874619876728939156834087671538472643803056884180462807352257190850903719523784903249439146394921183044961368855611775723180887308818786882877527138787565266652334928531866443585354813559898831309017970079782897003489408197715170007469077794826213151021050651149888076939814699036873504585934242172786610434043822677395370247857946479969888444983105125493523518937769933941833379913444634364076420953191349710439622088933989804120576151615160716034318451765541283396850836026385393248374148971229000076924838645581909672881324064006319772208905182990419969924046307216277753494088022903227791800569612391326909603223276530693051433047021548482887591477336572810400191180981871067195114936960955706826804604490482132156986576197308426795086236986564236871634948012128934801331824624699783370454466323163712816225734753722684119628305696016589976660636462946951175098238687142091448633087264431463267424322901965498502120904804980370509888508744010998956249617604576341758478908218273932694166136470310740237080452460629126241570694351236813491087746628150585412854720370952404576833452599724626360764093959236712965933143391123578320052238855120901147074502813187214699121116254549319335202323980455967305051376154448606497785115658201939560519177775881654865385083555350535092573803840241603783659582201039137406689159684638498457808474139159153590716535891397363780133569521977648307596835211895313617385079312506061026698703499484144395586010641462919293202416902072592584313262797991899885290297542946137772036270616777162714766213993267318860459617501854074902178410763984861515057957646562009723725346088087189109931052116068563162092034749684664172398227670616978905259552507509865950583429135265983151894378334196473254739480673610328289831350507436417213921486474300049651050090311281211619948276285412468026564151089989921127285676308082039599752445102206719039046192594452770036729305725597271886259279063859339126462686386149101048184017966556007118969135065138460712120267443696293502938256246521983174674867784049353746819501458074384242319862254149867465412189178813033218202911756849938715318907747109061849890877760464744985286201817254676707314239335058083966680369775931640991014494831908299911993694298143388217745170569393079407770991856397812630205802024375567922877335059306319510758753681207961781583986178863359751967296263391969831338868496201013728597023212361895339601099867926399008679339171094493544847100498538483033615076496169653374422699557544588363598522797898438730604636186840461471715099401406154843221037054977567379066615609666701401643354060946257112947564648467439871341444838281981219207202180921270461688602636063570035121780459549841309290459139403979260934835957241746293152258757404807532742179312122283782552955626040133883640699069848193538295997734931416832146219349782886724129381617963843789417635423076295748384731363850518530976206184371287266019548993669119020970839889184327471936827553999530412978841674837380136738363971222183404645242143096495449202328580494204907805436135887991429802859038185151237976420452572333950445067214365947276881508278305188632518456372093226937922548477750600231481194242812297527589723323738870366755720259691825997907009846507112314715617530890345697689715772808889090522901982967407785839331932749685312573543037615328670160976641898862261153025808544501861198805481463196140925711683486947913431870216347883893217925001274689499485042622041980579455068002830329015892104043122820164718448216061125453332833893895206782927176333498475663487573951226721348120318943471200981477645387409461216180713920862269232039497226015533393159150679626493498287069708343312656119323527193139670208901148935950197310332784416243345463882016526652911938590946300427375941098853425728297298244262588368553364839857084744754100136559537453824085480513776628096418143704236526965201288086669371379501441079007585327377608067752783165955671757863036398903615217807538483132083372272671674590611794908877996926420571046887469778840499519294965858125325276619973229720448107707742323801365495170526725778255131299360446570701044669670906390662472576757820440103064234473036421055675717541946248492665839699927613701110041055067020605578416436087171670850153463248726771468960164035341125837647057218441144169071931949062896583536378495037611063443966041880234402600946582573634304265823945861202920975850765298894955538510208759423024675765469468028725605547557758348160608135345426559557156654817985433448711695044239324721377959217073520338507240749117602213270916667737840733346306278460341461455051588408784685990424210186626804534588109197056413049031781201618470117023993164185186281801094360936199457087047935559102140607084815725037912212587111442938936799391425594474091482566939206422046621738501234746601021449305269278207925945784116482462490566441910650247739616525470172429864090899630106104270881710424736578548003277267888908614133991985632228991719517144808202952085449235504018565509099371586319435262284035002319947697634561706680091493814196191507741934394149899672207253358113852908173240195187423525475454998101288657686011331199910039044401504914394904652504880462150613351053374404228301963416752852653006606755570886383202865905191293163621706521176656341819132661296775567678198643817893480771182717998501469079429038191717265083788284510212893669345
(on preview, I see that Indistinguishable already did it for a big number).