Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><strong>It fails for much bigger numbers</strong>. The first prime is <strong>71</strong>, for that the candidate can fail. The smallest failing candidate for 71 is <strong>10986448536829734695346889</strong> which overshadows the number 10986448536829734695346889 + 142.</p> <pre><code>def primes(n, skip_range=None): """Modified "primes" with the original assertion from P.S. of the question. with skipping of an unimportant huge range. &gt;&gt;&gt; primes(71) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] &gt;&gt;&gt; # The smallest failing number for the first failing prime 71: &gt;&gt;&gt; big_n = 10986448536829734695346889 &gt;&gt;&gt; primes(big_n + 2 * 71, (72, big_n)) Traceback (most recent call last): AssertionError """ if not skip_range: primes = list(range(2, n + 1)) else: primes = list(range(2, skip_range[0])) primes.extend(range(skip_range[1], n + 1)) p = 0 while p &lt; len(primes): c = p + 1 while c &lt; len(primes): if(primes[c] % primes[p] == 0): primes.pop(c) if c &lt; len(primes): assert primes[c] % primes[p] != 0 c = c + 1 p = p + 1 return primes # Verify that it can fail. aprime = 71 # the first problematic prime FIRST_BAD_NUMBERS = ( 10986448536829734695346889, 11078434793489708690791399, 12367063025234804812185529, 20329913969650068499781719, 30697401499184410328653969, 35961932865481861481238649, 40008133490686471804514089, 41414505712084173826517629, 49440212368558553144898949, 52201441345368693378576229) for bad_number in FIRST_BAD_NUMBERS: try: primes(bad_number + 2 * aprime, (aprime + 1, bad_number)) raise Exception('The number {} should fail'.format(bad_number)) except AssertionError: print('{} OK. It fails as is expected'.format(bad_number)) </code></pre> <p>I solved these numbers by a complicated algorithm like a puzzle by searching possible remainders of n modulo small primes. The last simple step was to get the complete n (by chinese remainder theorem in three lines of Python code). I know all 120 basic solutions smaller than <a href="https://en.wikipedia.org/wiki/Primorial" rel="nofollow noreferrer">primorial</a>(71) = <code>2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71</code> repeated periodically by all multiples of this number. I rewrote the algorithm many times for every decade of tested primes because for every decade was the solution much slower than for the previous. Maybe I find a smaller solution with the same algorithm for primes 73 or 79 in acceptable time.</p> <hr> <p>Edit:</p> <p><strong>I would like to find also a complete silent fail</strong> of the unsafe original function. Maybe exists some candidate composed from different primes. This way of solution would only postpone the final outcome for later. Every step would be much more and more expensive for time and resources. Therefore only numbers composed from one or two primes are attractive.</p> <p>I expect that only two solutions the hidden candidate <em>c</em> are good: <code>c = p ** n</code> or <code>c = p1 * p ** n</code> or <code>c = p1 ** n1 * p ** n</code> where <em>p</em> and <em>p1</em> are primes and <em>n</em> is a power greater than 1. The <em>primes</em> function fails if <code>c - 2 * p</code> is divisible by no prime smaller than <em>p</em> and if all number between <em>c-2n</em> and <em>c</em> are divisible by any prime smaller than <em>p</em>. The variant p1*p**n requires also that the same <em>c</em> had failed before for <em>p1</em> (<em>p1 &lt; p</em>) as we already know infinite number of such candidates.</p> <p><strong>EDIT</strong>: I found a <strong>smaller example</strong> of failure: number 121093190175715194562061 for the prime 79. (which is about ninety times less than for 71) I can't continue by the same algorithm to find smaller examples because all 702612 basic solutions took more than 30 hours for the prime 79 on my laptop.</p> <p>I also verified it for all candidates smaller than 400000000 (4E10) and for all relevant primes, that no candidate will fail the assertion in the question. Until you have terabytes of memory and thousands years of time, the assertion in the algorithm will pass, because your time complexity is O((n / log(n)) ^2) or very similar.</p>
    singulars
    1. This table or related slice is empty.
    1. PODoes this prime function actually work?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. UShynekcer
    1. UShynekcer
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PODoes this prime function actually work?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COGreat job! I am not surprised that it fails (but I am impressed that you found a failure case).
      singulars
      1. PO
      1. USDaniel Fischer
    2. COWow! That looks pretty impressive, thanks for the answer! I'll have to read it again at some other time to fully undertand it, but you clearly know what you're doing. :-D
      singulars
      1. PO
      1. USphaz
    3. COconfirmed: `let x1=10986448536829734695346889 in filter (>50) $ map (head.factorize) [x1 .. x1+142]` ==> `[71,67,61,53,59,71]`.
      singulars
      1. PO
      1. USWill Ness
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload