A238729 Maximum flow of a number.

2, 3, 2, 5, 4, 7, 2, 3, 4, 11, 4, 13, 4, 6, 2, 17, 5, 19, 4, 6, 4, 23, 4, 5, 4, 3, 4, 29, 8, 31, 2, 6, 4, 10, 5, 37, 4, 6, 4, 41, 8, 43, 4, 6, 4, 47, 4, 7, 6, 6, 4, 53, 5, 10, 4, 6, 4, 59, 8, 61, 4, 6, 2, 10, 8, 67, 4, 6, 8, 71, 5, 73, 4, 8, 4, 14, 8, 79, 4, 3

Offset

2,1

Comments

F(n) is the maximal flow in a network whose nodes are the divisors of n, with an edge from a to b if and only if b/a is a prime factor of n, in which case the capacity of the edge is b/a. The source of the network is 1 and the sink is n.

Links

Alois P. Heinz, Table of n, a(n) for n = 2..10000

Wikipedia, Maximum flow problem

Wikipedia, Max-flow min-cut theorem

Formula

a(n) = min_{S:P([m])\{}} Product_{i:[m]\S} (e_i+1) * Sum_{i:S} p_i, where n = Product_{i=1..m} p_i^e_i and P([m]) is the powerset of {1,...,m}.

Maple

with(combinat):
a:= proc(n) local S, s, f, l, m;
      f:= infinity; l:= ifactors(n)[2]; m:= nops(l);
      S:= subsets({$1..m}):
      while not S[finished] do s:= S[nextvalue]();
        if s={} then next fi:
        f:= min(f, mul(1+l[i][2], i=({$1..m} minus s))*add(l[i][1], i=s))
      od; f
    end:
seq(a(n), n=2..100);  # Alois P. Heinz, Mar 04 2014

Mathematica

F[n_] := F[n] = Module[{v, e, flowgraph, flow},
   v = Divisors[n];
   e = Apply[DirectedEdge,
     Select[Subsets[v, {2}], PrimeQ[Last[#]/First[#]] &], {1}];
   flowgraph =
    Graph[e, EdgeCapacity -> Map[Rule[#, (Divide @@ Reverse[#])] &, e]];
   flow = FindMaximumFlow[flowgraph, 1, n, "OptimumFlowData"];
   flow["FlowValue"]]

Crossrefs

Sequence in context: A267807 A127433 A055573 * A182816 A367580 A195637

Adjacent sequences: A238726 A238727 A238728 * A238730 A238731 A238732

Keyword

nonn

Author

Ken Levasseur, Mar 03 2014

Status

approved