Vor
|
Registered User
|
|
|
May 5 |
comment |
how to prove a conjecture on a “canonical equivalent” of factoring @PaulTarau: ok, now it's clear. But it is a kind of cheating, because if you don't take into account the "cost" of delimiting the codes, one can consider valid this simpler representation, too: pick the binary representation of a number, then split it in an "array" assuming that every digit has a one on its left; so 360 = 101101000 becomes [01,0,000]. This representation except for n<2 is strictly "shorter" (in your sense) than b(n). |
|
May 4 |
comment |
how to prove a conjecture on a “canonical equivalent” of factoring What do you mean exactly with "succinct representation for the factoring of n"? For every succinct representation $r(\cdot)$, and for every m there is a number $n$ whose binary representation has length $m =b(n)$ that is incompressible (i.e. $|r(n)|\geq b(n)$. See Kolmogorov complexity, |
|
May 1 |
awarded | ● Commentator |
|
May 1 |
comment |
compression of a Turing machine run sequence @vzn: yes, you can look at [this short introduction by Lance Fortnow](people.cs.uchicago.edu/~fortnow/papers/…) |
|
Apr 30 |
comment |
compression of a Turing machine run sequence @AndreasBlass: indeed it's not too different from Sawin's idea :( ... there are also other variants (consider only states, include head directions, 0->1 1->0 transitions, crossing sections, ecc. ecc.); but obviously they all lead to the same highly compressible property. |
|
Apr 30 |
revised |
compression of a Turing machine run sequence deleted 1 characters in body |
|
Apr 30 |
answered | compression of a Turing machine run sequence |
|
Apr 20 |
comment |
A “bit” of primes @quid, @Greg Martin, I downloaded the papers and started to read the Prime Number Races (it seems the math version of a E.A.Poe novel :-)))) ); just another quick question (I'm definitively not an expert in number theory): given an arbitrary $p_n$ and an integer $l$ can we prove anything about the probability to find two equal consecutive "bit #1" sequences of length $l$ among the $p_i, i\leq n$? (perhaps it is worth a new question on mathoverflow :-) |
|
Apr 19 |
comment |
A “bit” of primes @quid: nice answer, I'll read (and try to understand :-) the suggested papers!!! thanks |
|
Apr 19 |
comment |
A “bit” of primes @quid: according to some tests I made they seems to be "powerful enough" to pass random tests like "diehard" (starting from an initial random prime $p_i$) ... |
|
Apr 19 |
asked | A “bit” of primes |
