12
$\begingroup$

Found this on Complexity Zoo warning expired certificate check NP Over The Complex Numbers.

[BCS+97] show the following striking result. For a positive integer $n$, let $t(n)$ denote the minimum number of additions, subtractions, and multiplications needed to construct $n$, starting from 1. If for every sequence ${n_k}$ of positive integers, $t(n_k k!)$ grows faster than polylogarithmically in $k$, then $P_C$ does not equal $NP_C$.

[BCS+97] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation, Springer-Verlag, 1997.

Couldn't find the paper online, so the exact definition would be helpful.

What are bounds for $t(n!)$?


Added later What are bounds for $t(a n!)$ where $a$ is nonzero and no other properties of $a$ are required?


Didn't spend much time, but couldn't solve this:

Find $a>1,k>1$ and $t(a k!) < t(k!)$.


Added I doubt this is of any practical interest because of the space complexity of factorial.

$$ n\log\left(\frac{n}{e}\right)+1 \leq \log n! $$

In OEIS A025201 a(n) = floor(log(n!))..

We have $n!=\Gamma(n+1)$ and $\log \log \Gamma(2^{1000})=699.6\ldots$ and $\log \log 2^{2^{1000}}=692.7\ldots$.

Even if an oracle computes the factorial, it is impossible to store in the computer space of all computers on earth.


Added later Comment from Gerhard "Wants To See Better Bounds" Paseman

I'd like to add that a similar sounding problem https://mathoverflow.net/a/75792/3206 using additions and multiplications has easy lower and upper bounds of O(log n). The computation model for this problem is different from the above problem, as "repeated subterms" do not add to the complexity of the computation, to state the matter (from memory) roughly. Gerhard "Wants To See Better Bounds" Paseman, 2015.01.26

References for the above answer in OEIS: http://oeis.org/A005245

$\endgroup$
  • $\begingroup$ This question would be much more likely to receive an expert answer at cstheory. However, unless something changed recently (unlikely), no nontrivial unconditional lower bounds on the arithmetic circuit complexity of $n!$ are known. $\endgroup$ – Emil Jeřábek Jan 24 '15 at 14:44
  • 1
    $\begingroup$ @EmilJeřábek Thanks, but I am interested from number theory point of view, not from complexity point of view. Don't like starting a "tag war" and would appreciate the numbertheory tag. $\endgroup$ – joro Jan 24 '15 at 14:49
  • 1
    $\begingroup$ But back to complexity: see rjlipton.wordpress.com/2009/02/23/factoring-and-factorials for a well-known connection of the problem to the complexity of factoring. $\endgroup$ – Emil Jeřábek Jan 24 '15 at 15:05
  • 1
    $\begingroup$ @EmilJeřábek OK, I am interested what number theorists say about this open problem. $\endgroup$ – joro Jan 24 '15 at 15:07
  • 1
    $\begingroup$ I'd like to add that a similar sounding problem mathoverflow.net/a/75792/3206 using additions and multiplications has easy lower and upper bounds of O(log n). The computation model for this problem is different from the above problem, as "repeated subterms" do not add to the complexity of the computation, to state the matter (from memory) roughly. Gerhard "Wants To See Better Bounds" Paseman, 2015.01.26 $\endgroup$ – Gerhard Paseman Jan 26 '15 at 22:30
12
+50
$\begingroup$

If Gerhard Paseman is right that $t(7!)=8$ then $(k,a)=(7,13)$ is already an example of $t(ak!)<t(k!)$, because $$ 13 \cdot 7! = 65520 = 2^{16} - 2^4 $$ can be reached in six steps from $1$: $$ 1 + 1 = 2, \quad 2 \cdot 2 = 4, \quad 4 \cdot 4 = 16, \quad 16 \cdot 16 = 256, \quad 256 \cdot 256 = 65536, $$ and finally $65536 - 16 = 65520$. This also makes $(10,1183)$ a candidate if $10!$ can't be reached as quickly as the seven steps to $65520^2$. [Added later: Michael Stoll now confirms that $t(7!)=8$ $-$ and also reports that it takes nine steps to reach $10!$, and eight for $8!$ and $9!$, so this seven-step route to $65520^2$ gives $t(ak!)<t(k!)$ also for $k=8,9,10$. Later yet, Stoll links to OEIS A217032 which gives the values of $t(k!)-1$ for all $k \leq 19$; this lets us give some more examples, such as $16! \, | \, (2^{64}-2^4)^4$ with $t(16!) = 13$ and $t((2^{64}-2^4)^4) \leq 11$.]

But the asymptotic question is much harder because we don't have good lower bounds on $t(k!)$. Gerhard Paseman gives an upper bound of $2k$ or maybe $(1+o(1))k$, which is within a constant factor of what can be done for any number of this size: if $N < k^k$ we can use $k$ additions to get $1,2,3,\ldots,k$, then $k-1$ multiplications to reach $k^2, k^3, \ldots, k^k$, and then $k+k$ more multiplications and additions to reach $N$ via its base-$k$ expansion. For $t(k!)$ we can reduce this by a factor $\gg \log k$ for large $k$, because $k!$ is a product of powers of the $\pi(k)$ primes $p\leq k$. We can reach all those primes in $\pi(k) + O(k^{1/2})$ additions: let $r = \lfloor \sqrt{k} \rfloor$, then add to get $1,2,3,\ldots,r,2r,3r,\ldots, r^2$, and each prime is a sum of one or two of these. [The Masked Avenger notes that it's a bit faster to first get all the numbers that occur as gaps $p_n - p_{n-1}$, and then get from each prime to the next.] Now use fewer than $\pi(k)$ multiplications to make the products $$ P_i := \prod_{ip \leq k < (i+1) p} p $$ for $i=1,2,3,\ldots,r$, and then $k! = P_1^{\phantom 1} P_2^2 P_3^3 \cdots P_r^r$ times $\pi(r)$ prime powers.

If that approach were optimal then we could get $t(ak!) < t(k!)$ by replacing $\prod_{i=1}^r P_i^i$ by $\left(\prod_{i=1}^r P_i\right)^{2^\rho}$ once $2^\rho \geq r$. But it seems that in fact $t(k) \ll k^{1/2 + o(1)}$ because one can write $m^2! = \prod_{j=0}^{m-1} Q(jm)$ where $Q(X) = (X+1) (X+2) (X+3) \cdots (X+m)$ and use FFT-like tricks to evaluate a degree-$m$ polynomial at $m$ points in only $m \log^A m$ operations. (See for instance this page. I learned of this surprising fact some year back from Henry Cohn. Caveat: some more work might be needed to fit this method into the $\{+,-,\times\}$ model without losing a factor worse than $k^\epsilon$. Added later: Turbo notes that this paper by Q.Cheng (of which more in the next paragraph) cites a paper by Strassen from the 1970's that gives a route to $k!$ in $O(k^{1/2} \log^2 k)$ $\{+,-,\times\}$ steps.)

This might be asymptotically optimal, but proving $t(k!) \gg k^{1/2}$ (or even $t(k) \gg k^\theta$ for some $\theta>0$) seems to be beyond reach. Meanwhile, Lenstra's ECM (elliptic curve method) for factoring suggests that $t(ak!)$ can be as small as $\exp O(\sqrt{\log k\,})$. Turbo gave this link to a 2004 paper by Qi Cheng that spells out this connection; that's perhaps surprisingly late, since Lenstra's ECM paper dates back to 1987 $-$ I found some e-mails from 1996 where I noted that ECM suggests that some multiple of $k!$ can be computed in a number of operations subexponential in $\log k$, and I wouldn't be surprised if Lenstra himself noticed this some years earlier. Note that likewise the counterexamples involving $2^{16}-2^4$ etc. that I started with are in effect using Pollard's $p-1$ factorization method.

I tried to estimate how well this would work for $k = 10^7$ compared with the prime-factorization technique. There are $664579$ primes $p < 10^7$, so any route to $k!$ via prime factorization would have to take at least $2 \cdot 664579$ steps (one to reach each $p$ and one to multiply by it).
For the ECM approach to some multiple of $k!$, I tried the following experiment. For each of the first $96$ isogeny classes of rank-$1$ elliptic tables in Cremona's table (these being the first two columns of Table 2 on page 235 of his Algorithms for Modular Elliptic Curves, covering conductors $N \leq 220$), choose a curve $E_i$ and a generator $P_i$ ($i \leq 96$). Then, for each prime $p \leq 10^7$, factor the order of each $P_i \bmod p$ using the built-in gp command ellorder, factor it as $\prod_j l_j^{e_j}$, and note the minimal value $m(p)$ of $\max_j l_j^{e_j}$ over the $96$ choices of $(E_i,P_i)$; thus for each $p$ there's some $i$ for which the order of $P_i \bmod p$ is a product of prime powers $\leq m(p)$. This took a few hours. The largest $m(p)$ observed is $379$, for $p = 6978421$. But about 90% of these primes have $m(p) \leq 83$. (There are $67608$ primes $p\leq 10^7$ with $m(p)>83$; also $47193$ with $m(p)>100$ and $22518$ with $m(p)>113$.) There are $23$ primes $l \leq 83$; let $M = 2^6 3^4 5^2 7^2 \prod_{l=11}^{83} l$, and compute for each $i$ a nonzero multiple $D_i$ of the denominator of $M P_i$, which requires about $150$ group-law additions in $E_i$ because $M \approx 2^{122.6}$. Then form $\prod_{i=1}^{96} D_i$, multiply by the product of the $67608$ missing primes, and square the whole thing $23$ times to get a multiple of $10^7!$. I don't know how many arithmetic operations it takes these days to do an elliptic-curve addition or subtraction, but it must be under $40$, and this already puts us under half our estimate for computing $10^7!$ itself via prime factorization ($96 \cdot 150 \cdot 40 = 600000$). There's probably a significant additional factor to be saved by using more curves $E_i$, balancing the $m(p)$ cutoff, and choosing $E_i$ that allow for faster group operations such as Edwards curves.

$\endgroup$
  • $\begingroup$ Is some factorization algorithm which "factors" k! of use, say Rho: en.wikipedia.org/wiki/Pollard%27s_rho_algorithm $\endgroup$ – joro Jan 31 '15 at 7:12
  • 1
    $\begingroup$ That's a good thought, but it seems one can compute $k!$ itself determinstically in $k^{1/2+\epsilon}$ operations, and (as in effect noted by Turbo) if you use ECM (the elliptic curve method for (the elliptic curve method for finding moderately-sized prime factors of large numbers) you get a heuristically subexponential route to some large multiple of $k!$. I intend to write more about this, but not now because I must go to sleep! $\endgroup$ – Noam D. Elkies Jan 31 '15 at 7:19
  • $\begingroup$ Good night :) So we are trying to compute a multiple of primorial as fast as possible and then keep squaring. $\endgroup$ – joro Jan 31 '15 at 7:38
  • 1
    $\begingroup$ @NoamD.Elkies Strassen has a technique which constructs $k!$ with ring operations in $O(k^{1/2}log k)$ steps. Again refer page 2 in cs.ou.edu/~qcheng/paper/factorial.pdf gives references 4,14. So we know at every k large enough $t(k!)\approx ck^{1/2+\epsilon}$ holds ($k$ need not be a square). $\endgroup$ – T.... Jan 31 '15 at 19:54
  • 1
    $\begingroup$ PS. This is the paper already mentioned in Turbo's answer. $\endgroup$ – Michael Stoll Feb 1 '15 at 13:47
5
$\begingroup$

$t(ak!)$ could have sub-exponential complexity (atleast in a randomized sense) at some $a\in\Bbb N$. Please refer interesting paper http://www.cs.ou.edu/~qcheng/paper/factorial.pdf.

My personal opinion is there is no polynomially many $\{+,-,\times\}$-operation algorithm to construct factorial in a deterministic sense.

However I do believe one of the two possibilities (possibly both) to be true:

  1. The $exp(\sqrt{\log n})$ can be brought to $O((\log n)^c)$ in a randomized sense at a fixed $c>0$.

  2. No deterministic algorithm can achieve $O((\log n)^c)$ $\{+,-,\times\}$-operations at any fixed $c>0$.

$\endgroup$
  • $\begingroup$ so it may very well be unthinkable could happen ultimately. $\endgroup$ – T.... Jan 31 '15 at 6:38
  • $\begingroup$ FYI extended the question for bounds for $t(a n!)$ for nonzero $a$. $\endgroup$ – joro Feb 3 '15 at 16:07
  • $\begingroup$ From complexity point of view, is computing multiple of factorial as powerful as computing factorial? IIRC sub-exponential SAT solver might cause troubles. $\endgroup$ – joro Feb 9 '15 at 15:55
  • $\begingroup$ If we guarantee the multiple avoids primes of interest. then yes. $\endgroup$ – T.... Feb 9 '15 at 21:47
4
$\begingroup$

The post above has a link to the term-complexity measure based on size of a term computing a number. The following different model is from my memory of the BCSS paper, so verification would be appreciated.

For this problem, I define a computation string be a finite sequence of integers $a_i$, with $ 1 \leq i \leq n$, which obeys the following properties:

  1. $a_1 = 1$
  2. For every $i$ with $1 \lt i \leq n$, there is an allowed operation (say $++$) and indices $j$ and $k$ with $1 \leq j,k \lt i$ such that $a_i= a_j ++ a_k$. Note that $j$ can equal $k$.

Then over all such computation strings of varying lengths which contain an integer $s$, pick the shortest one, say of length $n$, and set $t(s)=n$.

Generally the allowed operations are total and are a fixed finite set, specified in advance. For the set with addition, subtraction, and multiplication, one can form at most $(n!)^23^n$ distinct computation strings of length $n+1$, and one can use associativity and commutativity to cut down on the bound. It is clear the largest number formed is $2^{2^n}$ in a computation string of length $n+1$. It is not clear that one can arrange a computation of $s$ of length $t(s)$ and at the same time avoid repeats as well as having $a_{i+1}$ depend on $a_i$ for all $1 \lt i \lt n$. Indeed one may need to compute two or three numbers of complexity $t$ and put them in the string for later use.

I hope to update this with a small program that does efficient listing of small computation strings, so that one can get an idea of how $t(n!)$ grows with $n$.

EDIT 2015.01.29 Awk code added to generate small computation strings

BEGIN{ SEP= "," ; SEP2 = ";" ; MAX = 40
heap[1]= SEP2 1  #empty computation string followed by possible values for next value
for(newidx=idx=1; newidx < MAX; idx++) {
   # read next computation string and possible next values
   split(heap[idx],stuff,SEP2) ; csqlen=split(substr(stuff[1],1+length(SEP)),csq,SEP)
   vlen=split(stuff[2],vs,SEP)
   for(i=1; i<= vlen; i++) {val=vs[i]
      scsqval=sortme(val); print "Sorted" scsqval
      if ( !(scsqval in db) ) { db[scsqval]=1; outv=""
         addvalues(val,val)
         for(j=1; j <= csqlen; j++) { addvalues((v=csq[j]), val) }
         for(j=1; j <= vlen; j++) { newvals[vs[j]]=1 }      
         ### remove redundant values
         for(j=1; j <= csqlen; j++) { if ((v=csq[j]) in newvals) delete newvals[v] }
         if (val in newvals) delete newvals[val]
         for (v in newvals) { outv = outv SEP v; delete newvals[v] }
         newidx++; heap[newidx] = stuff[1] SEP val SEP2 substr(outv,1+length(SEP))
         print heap[newidx] } }
    for (v in csq) delete csq[v]; for (v in vs) delete vs[v]; for (v in stuff) delete stuff[v]}
}  


function addvalues(a,b) {  newvals[a*b]=newvals[a+b]=newvals[a-b]=newvals[b-a]=1 }

function sortme(vv){ tmps=""
  for(ii=1; ii<=csqlen;ii++) ccsq[ii]=csq[ii]
  ccsq[(newlen=csqlen+1)]=vv
  for(ii=1; ii<=newlen;ii++)  for(jj=ii+1; jj <= newlen; jj++) {
          if (ccsq[ii] > ccsq[jj]) { t=ccsq[jj] ; ccsq[jj]=ccsq[ii] ; ccsq[ii]=t } }
  for(ii=1; ii<=newlen;ii++) {tmps = tmps SEP ccsq[ii] ; delete ccsq[ii] }
  return tmps }

END EDIT 2015.01.29

ADDED 2015.01.30

I am running computations to get strings of length 8. I invite verification of the following tuples $(i,t[i])$: (1,1) (2,2) (6,4) (24,5) (120,7) (720,7) (5040,8) .

Of course one has $t[n!]$ is less than $2n$, and by using prime powers and certain assumptions on the distribution of primes, one can likely prove that for every $\epsilon$ there is $n_0$ so that for $n > n_0$ one has $t[n!] \lt (1 + \epsilon) n$. If one did not have subtraction, it might be possible to prove a linear in $n$ lower bound on $t[n!]$.

The number of computationally distinct terms (I identify permuted strings) follows the pattern (1,1) (2,2), (3,3) (4,7) (5,25) (6,115) (7,714) (8,x) where x is at least 2403. If anyone verifies these numbers, I invite them to make an OEIS entry.

END ADDED 2015.01.30

Gerhard "Ask Me About Small Programming" Paseman, 2015.01.27

$\endgroup$
  • $\begingroup$ As a check in understanding the model for plus, times and minus, I have 1 1, 1 0, and 1 2 as length 2 computation strings. Tossing out redundant and computationally equivalent strings, I get 1 0 -1, 1 0 2, 1 2 -1, 1 2 3, and 1 2 4 as (isomorphism class representatives of) strings of length 3. Gerhard "But Still Having Super-Exponential Growth" Paseman, 2015.01.27 $\endgroup$ – Gerhard Paseman Jan 27 '15 at 21:32
  • $\begingroup$ Rough upper bound will be the solution with 1s "compressed". Common terms reused and long sums (if any) computed faster. In the solution with 1s they use the inequality ||a+b|| <= ||a||+||b|| and ||a b|| <= ||a||+||b||. I am not sure these hold for t(n). $\endgroup$ – joro Jan 29 '15 at 6:22
  • $\begingroup$ Actually, stronger inequalities hold, as the computations for a and b will share at least 1 common term, usually more. So norm(a op b) will be at most norm(a) + norm(b) - 1, since the 1 does not have to be repeated. The lower bounds are what are important. Gerhard "Ask Me About Integer Complexity" Paseman, 2015.01.29 $\endgroup$ – Gerhard Paseman Jan 29 '15 at 18:46
  • $\begingroup$ Further, if you analyze the small sequences, you will find a lot of "converging" paths, and not so many "diverging" paths. So the inequality above will be sharp almost none of the time. Gerhard "Still Looking For Better Bounds" Paseman, 2015.01.29 $\endgroup$ – Gerhard Paseman Jan 29 '15 at 18:48
  • $\begingroup$ Appears the inequalities are of use :). So you can't prove it with lower bound because of 2^{2^n}} and similar? $\endgroup$ – joro Jan 30 '15 at 8:21
4
$\begingroup$

(Added 2015-02-01)

Perhaps the most relevant part of this answer is the reference to A217032, which gives the following values for $t(n!)$, $1 \le n \le 19$: $$1,2,4,5,7,7,8,9,9,10,10,11,12,12,13,13,13,14,14.$$

The problem whether $t(n!)$ can be bounded by a polynomial in $\log n$ (in the paper by Shub and Smale, see near the bottom of this answer) must be open, since a positive answer would imply a polynomial time factorization algorithm (assuming a straight-line program for $n!$ can also be constructed in time polynomial in $\log n$).


My comments to Gerhard Paseman's answer get a bit many and long, so it may be better to put all of this together in an answer.

I use the following Magma code to find all possible computations up to a given length.

step := func<s | {t : a, b in s, f in ['+','-','*'] | #t gt #s where t := Include(s, f(a,b))}>; gens := [{{1}}]; for n := 2 to 8 do l := gens[#gens]; Append(~gens, &join{step(s) : s in l}); end for;

The result of the computation is a set of integers; the next step adds an element that is a sum, difference or product of two elements in the set. I keep only sets that are larger than before, i.e., computations that do not repeat numbers. The numbers of these sets for lengths 1 to 8 are

1, 2, 5, 20, 149, 1852, 34354, 873386.

The counts for the number of distinct integers that can be computed are

1, 3, 6, 13, 38, 153, 867, 6930.

The factorials $n!$ first show up at step 1, 2, 4, 5, 7, 7, 8 (for $1 \le n \le 7$). No other factorial occurs up to length 8.

There are two computations of length 4 that compute 6: (1, 2, 3, 6) and (1, 2, 4, 6).

There is only one of length 5 for 24: (1, 2, 4, 6, 24).

There are close to 50 computations of length 7 for 120, but only five for 720:

(1, 2, 3, 9, 27, 729, 720), (1, 2, 3, 9, 81, 729, 720), (1, 2, 3, 9, 81, 80, 720), (1, 2, 4, 6, 24, 30, 720) and (1, 2, 4, 16, 20, 36, 720).

(All of this up to permutation.) There are 20 computations of length 8 of 5040, some of them containing 8 and 72, for example (1, 2, 4, 8, 9, 72, 70, 5040). It follows that $t(8!) = t(9!) = 9$. In fact, there are 94 computations of $8!$ and 18 of $9!$. I did run through all length-9 computations to check that (and also that $10!$ does not show up, so $t(10!) \ge 10$), generating them from the length-8 sets in gens[8], which took a few minutes, but I couldn't save all length-9 computation sets, because there are too many.

Added later: $t(10!) = 10$, one possibility being $(1,2,3,5,7,12,144,720,720^2,10!)$.

Further results:

  • For all $n \ge 10$, $t(n!) \ge 10$.
  • $t(11!) = 10$, for example $(1,2,3,9,81,80,77,720,720^2,11!)$

Thomas Sauvaget in the comment below points out that the sequence 1, 3, 6, 13, 38, ... mentioned above is A216999 in the OEIS (see also A173419). The OEIS links to this paper by Shub and Smale [this is probably what the book [BCS+97] that is mentioned in the Question refers to], where the following problem is formulated on page 3:

Problem. Is there a constant $c$ such that $$\tau(k!) \le (\log k)^c$$ for all $k$?

Their $\tau(n)$ is our $t(n)$. This is then related to the "intractability" of the Hilbert Nullstellensatz over $\mathbb C$.

From looking at the references to this paper in MathSciNet, my impression is that this problem is still open, but it is hard to know for sure.

The sequence $(t(n!)-1)$ is A217032. This gives the following values for $t(n!)$, $1 \le n \le 19$: $$1,2,4,5,7,7,8,9,9,10,10,11,12,12,13,13,13,14,14.$$ (Which is consistent with the data I have computed, but goes quite a bit further.)

$\endgroup$
  • 3
    $\begingroup$ It seems that the OEIS has 1, 3, 6, 13, 38, 153, 867, 6930 as A216999 with some more references. $\endgroup$ – Thomas Sauvaget Jan 31 '15 at 20:58
  • $\begingroup$ Since you ask about line breaks in comments, here is latex approach. I believe this can be done in a single texttt$$\texttt{line1}$$ $$\texttt{line2}$$ $\endgroup$ – joro Feb 1 '15 at 6:42
  • $\begingroup$ FYI extended the question for bounds for $t(a n!)$ for nonzero $a$. $\endgroup$ – joro Feb 3 '15 at 16:05
0
$\begingroup$

Here is partial result about multiple of factorial based on heuristic code.

By the paper Michael Stoll cites,

$t(m) \le 2 \log{m}$.

By repeated squaring $t(a^{2^k}) \le t(a)+k$.

Let $M=\log{n}$ and $S=\{a \cdot b^{2^k}+c : 1\le a \le 2M, 1\le b\le 2M, - 2M \le c \le 2M, 0\le k \le M\}$.

First we try to compute primorial $n$ and then square few times.

Members of $S$ can be computed in polynomial in $\log{n}$ time.

So it depends if few members of $S$ contain all primes $\le n$.

Let $\{P\}$ be the set of primes $\le n$.

Greedy Algorithm 1. For $ a,b \in S$ and $c= a \{+,-,\times\} b$ find the $c$ which is divisible by largest number of members of $P$. Keep $c$ and remove the primes from $P$. Repeat. Terminate when $P$ is empty. I can't prove this always terminate ;).

Certainly $S$ can be extended by the other answers.

Here is algorithm (1) for multiples of $45\#$ and $55\#$:

sage: greedyfactorial(45,planc=False,allb=1)
#S= 1637
1 9 [2, 3, 5, 7, 11, 13, 17, 31, 41] -340282366920938463463374607431768211200 = (1*2^8+0)-(1*2^128+0)
early 2 5 [19, 23, 29, 37, 43] 10301051460877537454126135158480 = (1*5^16+6)+(3*3^64+6)
sage: greedyfactorial(55,planc=False,allb=1)
#S= 5821
1 11 [2, 3, 5, 7, 11, 13, 17, 19, 31, 37, 41] -39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627973529600 = (1*2^24+0)-(1*2^384+0)
2 4 [23, 29, 47, 53] 19295810734578656668031216686940366563098640636282442092649989 = (6*2^8+1)*(2*2^192+5)
early 3 1 [43] 258 = 1+(1*2^8+1)

Sage code written in a hurry:

def greedyfactorial(n,deg=2,allb=True,planc=False):
    pri=list(primes(2,n+1)) #primorial
    k=floor(log(n))^deg
    lk=2*floor(log(n))
    pri1=[ 0 .. lk ]        
    pows=[]
    for p in pri1:
        if p==0:  continue
        for e in [ 2 .. lk]:
            pows += [p**(2**e)]
    pri1=[(i,str(i)) for i in pri1[:]]
    S=pri1[:]
    ca={}
    for p,_ in S:  ca[p]=1

    for p,_ in pri1:
      for q,_ in pri1:
        for b in pows:
            T=p*b+q
            if T in ca:  continue
            ca[T]=1
            S += [(p*b+q,'('+str(p)+'*'+str(factor(b))+ '+'+str(q)+')')]
            T=p*b-q
            if T in ca:  continue
            ca[T]=1
            S += [(p*b+q,'('+str(p)+'*'+str(factor(b))+ '-'+str(q)+')')]
    S=[(i,j) for i,j in S if i!=0]
    B=[(1,'1')]
    if allb:  B=S

    ops2=[ (lambda x,y:  x*y,'*'),(lambda x,y:  x + y,'+'), (lambda x,y:   x - y,'-')]
    print '#S=',len(S)
    def countp(A,S):
        r=[]
        for p in S:
            if A%p==0:  r += [p]
        return r    

    S=uniq(S)

    for ste in [ 1 .. k]:
        ma,br,BA=0,[],0
        for a,an in S:
            #for b,bn in S:
            for b,bn in B:
                for f,o in ops2:
                    A=f(a,b)
                    if A==0:  continue
                    r=countp(A,pri)
                    if len(r)>ma:
                        br=r
                        bs=an+o+bn
                        ma=len(r)
                        BA=A
                        if ma==len(pri):
                            print 'early',ste,ma,br,BA,'=',bs
                            return
                    if planc and ma>=len(pri)//2:  break    
                if planc and ma>=len(pri)//2:  break    

        print ste,ma,br,BA,'=',bs
        pri=[p for p in pri if not p in br]
        if pri==[]:
            print ' Done'
            return
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.