Considérons une expression 2^2^...^2avec des nopérateurs ^. Opérateur ^signifie exponentiation ("au pouvoir de"). Supposons qu'il n'y ait pas d'assosivité par défaut, donc l'expression doit être entièrement entre parenthèses pour devenir sans ambiguïté. Le nombre de façons de mettre l'expression entre parenthèses est donné par des nombres catalans C_n=(2n)!/(n+1)!/n! .

Parfois, des parenthèses différentes donnent le même résultat numérique, par exemple (2^2)^(2^2)=((2^2)^2)^2, de sorte que le nombre de différents résultats numériques possibles pour un donné nest inférieur à celui C_nde tous n>1. La séquence commence 1, 1, 2, 4, 8, ...par opposition aux nombres catalans1, 2, 5, 14, 42, ...

Le problème est d'écrire le programme (ou la fonction) le plus rapide qui accepte nen entrée et renvoie le nombre de résultats numériques différents possibles de l'expression 2^2^...^2avec des nopérateurs ^. Les performances ne devraient pas se détériorer de manière significative au fur et à mesure de leur ncroissance, donc le calcul direct des tours de forte puissance est probablement une mauvaise idée.

Python 2.7

Cette approche tire parti des considérations suivantes:

Tout entier peut être représenté comme une somme de puissances de deux. Les exposants aux pouvoirs de deux peuvent également être représentés comme des pouvoirs de deux. Par exemple:

8 = 2^3 = 2^(2^1 + 2^0) = 2^(2^(2^0) + 2^0)

Ces expressions avec lesquelles nous nous retrouvons peuvent être représentées comme des ensembles d'ensembles (en Python, j'ai utilisé le intégré frozenset):

• 0devient l'ensemble vide {}.
• 2^adevient l'ensemble contenant l'ensemble représentant a. Par exemple: 1 = 2^0 -> {{}}et 2 = 2^(2^0) -> {{{}}}.
• a+bdevient la concaténation des ensembles représentant aet b. Par exemple,3 = 2^(2^0) + 2^0 -> {{{}},{}}

Il s'avère que les expressions du formulaire 2^2^...^2peuvent facilement être transformées en leur représentation d'ensemble unique, même lorsque la valeur numérique est beaucoup trop grande pour être stockée sous forme d'entier.

Pour n=20, cela s'exécute en 8.7s sur CPython 2.7.5 sur ma machine (un peu plus lent en Python 3 et beaucoup plus lent en PyPy):

"""Analyze the expressions given by parenthesizations of 2^2^...^2.

Set representation:  s is a set of sets which represents an integer n.  n is
  given by the sum of all 2^m for the numbers m represented by the sets
  contained in s.  The empty set stands for the value 0.  Each number has
  exactly one set representation.

  In Python, frozensets are used for set representation.

  Definition in Python code:
      def numeric_value(s):
          n = sum(2**numeric_value(t) for t in s)
          return n"""

import itertools


def single_arg_memoize(func):
    """Fast memoization decorator for a function taking a single argument.

    The metadata of <func> is *not* preserved."""

    class Cache(dict):
        def __missing__(self, key):
            self[key] = result = func(key)
            return result
    return Cache().__getitem__


def count_results(num_exponentiations):
    """Return the number of results given by parenthesizations of 2^2^...^2."""
    return len(get_results(num_exponentiations))

@single_arg_memoize
def get_results(num_exponentiations):
    """Return a set of all results given by parenthesizations of 2^2^...^2.

    <num_exponentiations> is the number of exponentiation operators in the
    parenthesized expressions.

    The result of each parenthesized expression is given as a set.  The
    expression evaluates to 2^(2^n), where n is the number represented by the
    given set in set representation."""

    # The result of the expression "2" (0 exponentiations) is represented by
    # the empty set, since 2 = 2^(2^0).
    if num_exponentiations == 0:
        return {frozenset()}

    # Split the expression 2^2^...^2 at each of the first half of
    # exponentiation operators and parenthesize each side of the expession.
    split_points = xrange(num_exponentiations)
    splits = itertools.izip(split_points, reversed(split_points))
    splits_half = ((left_part, right_part) for left_part, right_part in splits
                                           if left_part <= right_part)

    results = set()
    results_add = results.add
    for left_part, right_part in splits_half:
        for left in get_results(left_part):
            for right in get_results(right_part):
                results_add(exponentiate(left, right))
                results_add(exponentiate(right, left))
    return results


def exponentiate(base, exponent):
    """Return the result of the exponentiation of <operands>.

    <operands> is a tuple of <base> and <exponent>.  The operators are each
    given as the set representation of n, where 2^(2^n) is the value the
    operator stands for.

    The return value is the set representation of r, where 2^(2^r) is the
    result of the exponentiation."""

    # Where b is the number represented by <base>, e is the number represented
    # by <exponent> and r is the number represented by the return value:
    #   2^(2^r) = (2^(2^b)) ^ (2^(2^e))
    #   2^(2^r) = 2^(2^b * 2^(2^e))
    #   2^(2^r) = 2^(2^(b + 2^e))
    #   r = b + 2^e

    # If <exponent> is not in <base>, insert it to arrive at the set with the
    # value: b + 2^e.  If <exponent> is already in <base>, take it out,
    # increment e by 1 and repeat from the start to eventually arrive at:
    #   b - 2^e + 2^(e+1) =
    #   b + 2^e
    while exponent in base:
        base -= {exponent}
        exponent = successor(exponent)
    return base | {exponent}

@single_arg_memoize
def successor(value):
    """Return the successor of <value> in set representation."""
    # Call exponentiate() with <value> as base and the empty set as exponent to
    # get the set representing (n being the number represented by <value>):
    #   n + 2^0
    #   n + 1
    return exponentiate(value, frozenset())


def main():
    import timeit
    print timeit.timeit(lambda: count_results(20), number=1)
    for i in xrange(21):
        print '{:.<2}..{:.>9}'.format(i, count_results(i))

if __name__ == '__main__':
    main()

(Le concept du décorateur de mémorisation est copié à partir de http://code.activestate.com/recipes/578231-probably-the-fastest-memoization-decorator-in-the-/ .)

Production:

8.667753234
0...........1
1...........1
2...........1
3...........2
4...........4
5...........8
6..........17
[...]
19.....688366
20....1619087

Timings pour différents n:

 n    time
16    0.240
17    0.592
18    1.426
19    3.559
20    8.668
21   21.402

Toute valeur nsupérieure à 21 entraîne une erreur de mémoire sur ma machine.

Je serais intéressé si quelqu'un pouvait rendre cela plus rapide en le traduisant dans une autre langue.

Edit: optimisé la get_resultsfonction. En outre, l'utilisation de Python 2.7.5 au lieu de 2.7.2 l'a rendu un peu plus rapide.

C #

Il s'agit d'une traduction du code Python de flornquake en C # en utilisant une routine d'ajout de niveau inférieur qui fournit une accélération modérée par rapport à une traduction directe. Ce n'est pas la version la plus optimisée que j'ai, mais c'est un peu plus long car il doit stocker la structure arborescente ainsi que les valeurs.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox {
    class PowerTowers {
        public static void Main() {
            DateTime start = DateTime.UtcNow;
            for (int i = 0; i < 17; i++)
                Console.WriteLine("{2}: {0} (in {1})", Results(i).Count, DateTime.UtcNow - start, i);
        }

        private static IList<HashSet<Number>> _MemoisedResults;

        static HashSet<Number> Results(int numExponentations) {
            if (_MemoisedResults == null) {
                _MemoisedResults = new List<HashSet<Number>>();
                _MemoisedResults.Add(new HashSet<Number>(new Number[] { Number.Zero }));
            }

            if (numExponentations < _MemoisedResults.Count) return _MemoisedResults[numExponentations];

            HashSet<Number> rv = new HashSet<Number>();
            for (int i = 0; i < numExponentations; i++) {
                IEnumerable<Number> rhs = Results(numExponentations - 1 - i);
                foreach (var b in Results(i))
                    foreach (var e in rhs) {
                        if (!e.Equals(Number.One)) rv.Add(b.Add(e.Exp2()));
                    }
            }
            _MemoisedResults.Add(rv);
            return rv;
        }
    }

    // Immutable
    struct Number : IComparable<Number> {
        public static Number Zero = new Number(new Number[0]);
        public static Number One = new Number(Zero);

        // Ascending order
        private readonly Number[] _Children;
        private readonly int _Depth;
        private readonly int _HashCode;

        private Number(params Number[] children) {
            _Children = children;
            _Depth = children.Length == 0 ? 0 : 1 + children[children.Length - 1]._Depth;

            int hashCode = 0;
            foreach (var n in _Children) hashCode = hashCode * 37 + n.GetHashCode() + 1;
            _HashCode = hashCode;
        }

        public Number Add(Number n) {
            // "Standard" bitwise adder built from full adder.
            // Work forwards because children are in ascending order.
            int off1 = 0, off2 = 0;
            IList<Number> result = new List<Number>();
            Number? carry = default(Number?);

            while (true) {
                if (!carry.HasValue) {
                    // Simple case
                    if (off1 < _Children.Length) {
                        if (off2 < n._Children.Length) {
                            int cmp = _Children[off1].CompareTo(n._Children[off2]);
                            if (cmp < 0) result.Add(_Children[off1++]);
                            else if (cmp == 0) {
                                carry = _Children[off1++].Add(One);
                                off2++;
                            }
                            else result.Add(n._Children[off2++]);
                        }
                        else result.Add(_Children[off1++]);
                    }
                    else if (off2 < n._Children.Length) result.Add(n._Children[off2++]);
                    else return new Number(result.ToArray()); // nothing left to add
                }
                else {
                    // carry is the (possibly joint) smallest value
                    int matches = 0;
                    if (off1 < _Children.Length && carry.Value.Equals(_Children[off1])) {
                        matches++;
                        off1++;
                    }
                    if (off2 < n._Children.Length && carry.Value.Equals(n._Children[off2])) {
                        matches++;
                        off2++;
                    }

                    if ((matches & 1) == 0) result.Add(carry.Value);
                    carry = matches == 0 ? default(Number?) : carry.Value.Add(One);
                }
            }
        }

        public Number Exp2() {
            return new Number(this);
        }

        public int CompareTo(Number other) {
            if (_Depth != other._Depth) return _Depth.CompareTo(other._Depth);

            // Work backwards because children are in ascending order
            int off1 = _Children.Length - 1, off2 = other._Children.Length - 1;
            while (off1 >= 0 && off2 >= 0) {
                int cmp = _Children[off1--].CompareTo(other._Children[off2--]);
                if (cmp != 0) return cmp;
            }

            return off1.CompareTo(off2);
        }

        public override bool Equals(object obj) {
            if (!(obj is Number)) return false;

            Number n = (Number)obj;
            if (n._HashCode != _HashCode || n._Depth != _Depth || n._Children.Length != _Children.Length) return false;
            for (int i = 0; i < _Children.Length; i++) {
                if (!_Children[i].Equals(n._Children[i])) return false;
            }

            return true;
        }

        public override int GetHashCode() {
            return _HashCode;
        }
    }
}