[seqfan] Re: A program to compute A002845

Mon Feb 18 21:29:01 CET 2019

Using the sparse integer approach of Reshetnikov, I have verified the
existing terms of A002845 and computed

A002845(30) = 3948189131
A002845(31) = 9473431479

The value for a(30) is within the bound previously estimated by Reshetnikov.

To achieve these results, gzip compressed text representations of the
sparse integers were stored on disk rather than keeping them in RAM.  In
fact, during a given run, multiple sorted output files were written and
these files were subsequently merged with duplicate removal, then
compressed to produce the final result. Processing of individual cases was
slower because of the I/O, parsing, and compression costs.  During the
computation the same number can arise in multiple ways, e.g.
(2^2)^2=2^(2^2), and these duplicates need to be removed.  In Reshetnikov's
program this is accomplished by storing all the results in a set.  I also
used a set to remove some local duplicates, but the majority of the
duplicate removal happens externally using standard Linux tools sort
(actually running as a merge) and uniq.  Further, in computing the result
for a(n), parallel jobs were run for the cases s+t = n, s <= t, computing
both A^B and B^A where A iterates over all the solutions from a(s) and B
iterates over all the solutions from a(t).

This approach should work on machines with 32 GB RAM, but three virtual
machines with 96 GB RAM each were used here. Two jobs were run
simultaneously on each 96 GB cluster node. By far the slowest case was s=1.

The total elapsed time for a(30) was approximately 30 hours and resulted in
a 12 GB compressed output file.  The generation of initial uncompressed
output files for a(31) took 48 hours. A further 28 hours were spent
merging, removing duplicates, and compressing the final result down to 29
GB. Peak disk usage during computation of a(31) was approximately 1.2 TB
(including storage needed for all n < 31).

I do not intend to push this sequence any further at this time, but believe
the general approach should be sufficient to compute a(32) and perhaps a
few more terms.  The parallelism could be improved to spread the work more
evenly over a cluster, and a binary representation rather than a text
representation would remove the parsing cost.  I used gzip in its try hard
mode (gzip -9), a more modest compression level (or avoiding it altogether)
would be faster at the cost of increased storage.

Code for this sequence:

https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a002/A002845.java
https://github.com/archmageirvine/joeis/blob/master/src/irvine/math/SparseInteger.java

Sean.

On Sun, 10 Feb 2019 at 15:39, Vladimir Reshetnikov <v.reshetnikov at gmail.com>
wrote:

> A friend of mine, Kirill Osenkov, used my program and a computer with 432
> GB RAM to find the next two elements of the sequence, it took about 7
> hours; they are A002845(28) = 688,821,573 and A002845(29) = 1,647,853,491.
> He estimated the computation of the next term would require about 4TB RAM,
> but we are trying to come up with some ideas how to use less memory. Based
> on several extrapolation approaches, I expect that A002845(30) ≈
> 3,948,160,000 ± 300,000.
>
> Does anybody have an idea about asymptotic behavior of this sequence? The
> known values can be closely approximated by A002845(n) ≈ 0.34708262 *
> 2.518831816^n * (log(n) / n)^2.0941666.
>
> --
> Best regards
> Vladimir Reshetnikov
>
>
> On Thu, Jan 31, 2019 at 2:26 AM bacher <
> Roland.Bacher at univ-grenoble-alpes.fr>
> wrote:
>
> >
> > Nice. Thank you very much,
> >
> > Best wishes, Roland Bacher
> >
> > Vladimir Reshetnikov <v.reshetnikov at gmail.com> a écrit :
> >
> > > Yes, I believe there are.
> > >
> > > For example, the equality (((x^x)^x)^x)^x = ((x^x)^x)^(x^x) holds for
> x =
> > > 2, but does not hold for x = -0.0802980827... + 4.4082663977... i,
> > although
> > > it satisfies (x^x)^x = x^(x^x).
> > >
> > > --
> > > Best regards
> > > Vladimir Reshetnikov
> > >
> > >
> > > On Wed, Jan 30, 2019 at 6:06 AM bacher <
> > Roland.Bacher at univ-grenoble-alpes.fr>
> > > wrote:
> > >
> > >>
> > >> Are there any identities not coming from
> > >> ((2^2)^2)=(2^(2^2)) among such expressions?
> > >>
> > >> Best wishes, Roland Bacher
> > >>
> > >>
> > >> Vladimir Reshetnikov <v.reshetnikov at gmail.com> a écrit :
> > >>
> > >> > Today I published a program on GitHub that computes elements of
> > >> > https://oeis.org/A002845 (Number of distinct values taken by
> > 2^2^...^2,
> > >> > with n 2's and parentheses inserted in all possible ways).
> > >> >
> > >> > https://github.com/VladimirReshetnikov/Oeis.A002845
> > >> >
> > >> > It uses a special representation of numbers that allows to
> efficiently
> > >> > manipulate high power towers, but is still brute force in the sense
> > that
> > >> it
> > >> > enumerates and stores all possible outcomes for each n. So far I was
> > able
> > >> > to confirm all values currently listed (up to n=27), and I estimate
> > that
> > >> I
> > >> > would need a machine with more than 100GB RAM to compute the next.
> > >> >
> > >> > I would be delighted if anybody could improve my solution, port it
> to
> > >> other
> > >> > programming languages, or provide computational resources.
> > >> >
> > >> > --
> > >> > Best regards
> > >> > Vladimir Reshetnikov
> > >> >
> > >> > --
> > >> > Seqfan Mailing list - http://list.seqfan.eu/
> > >>
> > >>
> > >>
> > >> --
> > >> Seqfan Mailing list - http://list.seqfan.eu/
> > >>
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> >
> >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>