Sorry for the brevity I'm on a phone. This code computes g(n,p) which is the best g(n) where the factors are prime powers with the prime le p. It builds on this prime by prime. Then g(n,n) is g(n). On Nov 13, 2016 2:19 PM, "Tomas Rokicki" <rokicki@gmail.com> wrote: Read the code carefully. On Nov 13, 2016 2:17 PM, "Allan Wechsler" <acwacw@gmail.com> wrote:
Ooh, even worse: suppose N = p^k + M, and g(M) happens to be divisible by p^k? Then the product p^k*g(M) would look like a really good candidate for g(N), but would in fact have a spurious factor of p^k.
On Sun, Nov 13, 2016 at 5:15 PM, Allan Wechsler <acwacw@gmail.com> wrote:
It looks like this code depends on a lemma whose truth is not obvious to me.
"For any N, there exists a prime power p^k such that g(N) = g(N-p^k) * p^k."
It is conceivable to me that for any component p^k of g(N), g(N-p^k) might not be relatively prime to p^k. That is, it's conceivable that none of the cofactors of prime powers in g(N) are themselves optimal in the Landau sense. I admit that it doesn't seem _likely_, because you would have to have bad luck for every component p^k in g(N). But still conceivable. Am I missing an easy demonstration of this lemma?
On Sun, Nov 13, 2016 at 12:34 PM, Tomas Rokicki <rokicki@gmail.com> wrote:
Perhaps this code will be simple enough for most to follow.
Note that I use doubles and don't report the actual partition. This is trivial to do (just add an array storing the last prime power that improved a result, and then walk backwards from there).
This code easily handles 65536 and gives 2.41074e+388. Running it in Python (with its superior number stack) should give you an exact result pretty quickly; I can provide that if anyone is interested.
for (int i=0; i<N; i++) maxv[i] = 1 ; for (int i=2; i<=N; i++) { if (!isprime(i)) continue ; for (int j=N-1; j>=i; j--) { long double hi = maxv[j] ; for (long long pp=i; pp<=j; pp=pp*i) hi = max(hi, maxv[j-pp]*pp) ; maxv[j] = hi ; } } for (int i=0; i<N; i++) cout << i << " " << maxv[i] << endl ;
On Sun, Nov 13, 2016 at 9:09 AM, Tomas Rokicki <rokicki@gmail.com> wrote:
This is a pretty common programming contest problem. You can make an additional restriction as follows:
Every factor (except perhaps the last) should be a power of a prime. (If a factor is composite, you can factor it into prime powers and get equivalent impact with fewer base elements.)
Then, you can solve this problem using dynamic programming. First you solve it for n=1..65536 using only powers of 2. Then based on that you solve it for n=1..65536 using powers of 2 and powers of 3. Then you extend that with powers of 5, and so on and so forth; pretty straightforward.
You do need to use a programming language or library that supports bigints, or else you can represent the product by its logarithm.
This is not considered a difficult problem for modern college programming contests.
On Sun, Nov 13, 2016 at 4:02 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
I'm suffering some disconnection here: compare JA below
> The upper bound used for the downward search is truly enormous for n = 2^16.
with https://oeis.org/draft/A000793 comments
> Grantham mentions that he computed a(n) for n <= 500000.
--- citing a 1995 reference given later.
Yet 2^16 = 65536 < 500000 , and JG's hardware 20 years older!
WFL
On 11/13/16, Joerg Arndt <arndt@jjj.de> wrote:
* Allan Wechsler <acwacw@gmail.com> [Nov 13. 2016 08:33]: > [...] > > (Of all the code snippets in the relevant page at A000793, all of them > except one are clearly just enumerating partitions and comparing LCM's. > But > Charles Greathouse's PARI code is not doing anything like that, and I > don't > have a clue what it *is* doing.)
Charles' code seems to use what I just entered as a formula in A000793: For n>=2, A000793(n) = max_{k} A008475(k) <= n. Cf. https://oeis.org/draft/A000793
Is this correct?
The upper bound used for the downward search is truly enormous for n = 2^16.
> _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun