Monday, February 20, 2017

[uyyrhizz] IDE type annotations

Ideas for a desirable feature of a Haskell IDE:

Good: IDE pops up the type signature of the library function or symbol under the point.  Emacs haskell-mode can do this.

Better: IDE is aware of static scoping, let binding, and imports to really know what function you are referring to.  However, if you forgot to import, it still tries to be helpful, guessing at a library function and offering its signature as well as a reminder that you need to import it.

Better: If the function does not have an explicit type signature, the IDE does type inference to figure it out.

Better: if the type is polymorphic, the IDE also provides the type of the function as instantiated where it is used, instead of just the polymorphic type where it was declared.

Wednesday, February 15, 2017

[jjlddkmc] Pick your own house lock

Instead of leaving a concealed key outside the house for when one accidentally locks oneself out, leave lockpicks concealed outside the house.  This is less disastrous if someone bad discovers it.

Leaving the lockpicks at your house avoids needing to carry them on your person, possibly avoiding legal issues in jurisdictions where possession is considered proof of intent.

Of course, learn to pick your own house lock first.  This is aided by American tradition of having terribly insecure door locks in many places.

[lqdaenrs] Fun games of no strategy

Create a game which has no strategy (though it might present the illusion of requiring strategy) but which is still enjoyable to play.  One way is each time playing results in novel occurrences, perhaps through where simple rules can interact in interesting, beautiful, and complicated ways.  A randomizer can ensure new regions of the state space get explored each time.

[dptxehvj] Face CAPTCHA

Humans can presumably read faces, gauging emotion, better than computers.  This could be the basis for a CAPTCHA similar in style to reCAPTCHA: a bunch of pictures of faces that people form consensus on what emotion it is conveying.

[uxnvpywt] Free speech as a scapegoat

Enumerate historical examples in which free speech was blamed for a problem, speech was curtailed, and the problem persisted, thereby proving that speech was incorrectly blamed.

[jzvhfndr] Tor for C2

Brian Krebs reports that the command and control server for botnet was hosted by an ISP in Ukraine, and complaining up the ISP tree eventually knocked it offline.  However, such a server seems to be the perfect use case for a Tor hidden service.  Why was it not done?

Monday, February 13, 2017

[crhnyxty] Competent smuggler

In an alternate universe, Luke and Ben hire a different smuggler to transport themselves to Alderaan.  Perhaps someone more competent, less flying by the seat of his pants, who demonstrates a spectacular array of clever tricks to "avoid Imperial entanglements".  (Most of the time, Han, Chewbacca, and the Millennium Falcon rely only on speed and gunfire.)

[rnsmkgjj] Matter disappearing

Astronomy has a few nice examples of large quantities of matter turning into energy.

Of course, stellar nuclear fusion.

A supernova converts a large amount of the progenitor star into neutrinos.  While technically not massless, because neutrinos interact so little with anything, it seems like mass just disappeared.

In a black hole merger, a significant amount of mass gets radiated away as gravitational waves.

[lkajhfjz] Great glass elevator

It seems relatively easy to simulate in virtual reality the visual experience of traveling straight up and down.  There are many ways to do it, from projecting a fully real environment (previously, tower) to traveling in a completely synthesized world.

Consider altering the stereo depth, the distance between the eyes, at different heights.

Why do you want to be an astronaut?

[megjnlno] Copyright causes history not to be recorded

Artists have incentive not to record what influenced or inspired their artistic works because of fear of copyright lawsuits from those they cite.  But such documentation would be useful for historians.

This documentation might be significant beyond just curiosities of history: it might show how society is knitted together, which would be powerfully useful.

Inspired by Marvin Gaye Estate versus Blurred Lines.

[omgbdhjk] Panning and rotating rectangle

Tile a rectangular image, then place a rectangular viewport the same size as the image on the plane.  No matter the offset or orientation, exactly the entire image will be visible, though cut up.  (Is this fact interesting or obvious?)  Slide and turn the viewport around to offer different views of the same image.  Easiest is irrational slope and constant irrational rate of rotation, so the viewport will never repeat.

[fprrzelf] Copyright education at classical music concerts

Distribute educational material at performances regarding what copyright duration was when the performed work was created.

"XYZ was incentivized to compose the work you will hear tonight by copyright protection -- exclusive right to royalties -- of 0 years.  Compare this to copyright term for works composed nowadays: 95 years.  Is music better nowadays?"

Wednesday, February 08, 2017

[cmrfqpcl] Before and outside the Big Bang

The universe is and has always been infinite in size.  It has also existed forever in time.  We'll explain these assumptions later (tl;dr: Occam's Razor).  We are challenging the conventional notion that the universe had a start point in time, the Big Bang, and at that start point it was infinitesimally small.

A long time ago, the infinite universe was very hot and dense, so hot that the 4 known fundamental forces (gravity, strong, weak, EM) were merged into one.

Space expanded, so the universe got cooler.  Note that space remained infinite in size as it expanded, kind of like multiplying infinity by 2.  It's twice as large, but still infinity.  Things close together got further apart throughout the infinite universe as it expanded.

At some time point, Tgravity, it got cool enough for gravity to separate out from that one merged fundamental force.  Tgravity is a negative number for reasons we'll explain later.

Space expanded more, the universe got cooler, and at time point Tstrong, the strong nuclear force separated from the electroweak force.  Actually, we'll define Tstrong to be 0 for reasons we'll explain later.  So, immediately after this time 0, the forces were gravity, strong, and electroweak.

Space expanded (a lot) more, the universe got cooler, and the weak nuclear force separated from the electromagnetic force at time T_weak.  We actually know the value of T_weak to be about 10^-12 seconds based on particle accelerator experiments which can recreate the temperature of the universe (slightly) before T_weak.

We wrote above that space expanded "a lot" because, during some interval between 0 and T_weak, inflation happened.  It happened much closer to the 0 end.  More about that later.

The unconventional selection of Tstrong=0 is motivated by philosophical and practical considerations of what we can and cannot know.  There is a huge energy gap (10^12) between the electroweak and Grand Unified Theory scales: GUT explains the universe between Tgravity and 0, i.e., "negative time".  We will "never" be able to do experiments at the GUT scale: certainly not on Earth.  They are too unimaginably difficult: a trillion times more energy than the LHC.  Therefore we will never be able to know (that is, experimentally confirm) what the universe was like at or before time 0.  Incidentally, this means we will never know what time Tgravity was.

Similarly, we will never, ever, be able to experimentally confirm a Theory Of Everything (TOE) a.k.a quantum gravity a.k.a. string theory, a theory about what universe was like before the negative time point Tgravity, called the Planck scale.  In fact, time points before Tgravity might be ill-defined, because gravity separating out from the other forces means that only then did spacetime come to exist, so only then did time itself and consequently things like causality come to exist.  Before that point, timey-wimey wibbly wobbly.

(Maybe our descendants or alien civilizations will prove me wrong about what we can scientifically know, then we will regret this choice of zero (like Fahrenheit).  Scientific American's The Amateur Scientist did whimsically propose building an Ultimate Collider to test TOEs.)

Actually time might have also behaved funny during inflation: inflation did very strange things to space, so we speculate it also did strange things to spacetime and consequently time.  We may never understand inflation: it is so close to the GUT scale that experiments probing it seem almost as unimaginable as experiments testing a GUT.  It might have been better to define the end of inflation as the zero time point.  Only then did time start flowing the way we experience it now.  The quoted value of T_weak above is the time interval between the end of inflation and the end of the electroweak epoch.

Nevertheless, even though we will never know what the universe was like before time 0, we will assume that it always existed all the way out to negative infinity.  (We may need some yet undefined notion of what it means to exist before time itself began to exist at Tgravity.)  We assume infinite existence because it is the simplest model: Occam's Razor.  If we don't assume it, then we have to explain more complicated things: what existed before the universe burst into being?  Why did the universe burst into being?

Similarly, we assume that space is infinite. Currently, there is a finite patch of the universe we can see, because light has had time to reach our eyes.  Astronomers call this the Observable Universe, which is kind of a confusing name.  Better would have been Our Finite Patch Of The Universe.  Lots of confusion stems from conflating "universe" (assumed infinite) and "observable universe" (definitely not infinite).  Even though we cannot see beyond Our Finite Patch Of The Universe, we assume that the universe extends infinitely beyond it.  This is again the simplest model.  Otherwise we have to explain complicated things like, what does the edge of the universe look like?  What exists beyond the edge?

Similarly, we also assume that space has always been infinite.  At no point in time was the entire universe compressed into a point.  Things were denser and closer back then, but the extent of space was always infinite.  This is the simplest model: otherwise, we have to explain complicated things like, what existed outside of the finite (in fact zero-volume) point?  How did the universe transition instantaneously from 0 to infinite in size?

When cosmologists say, at such and such point in time, the universe was the size of a grain of sand, it is actually confusing shorthand for, the chunk of space that eventually expanded to Our Finite Patch Of The Universe was, back then, the size of a grain of sand.  It is just shorthand for the expansion factor between then and now.  That sand-grain-sized chunk of space back then was still part of an infinite universe.

The conventional narrative that the universe started from an infinitesimal point at the Big Bang is derived from running the equations of General Relativity backward in time.  If you do that, it does predict a singularity, and conventionally, that singular point is defined as the zero point in time, as opposed to a later point in time Tstrong defined as zero above.  However, running GR backwards all the way to the singularity is a little bit silly, because other things happen on the way to the singularity, namely some GUT, some TOE, which might interfere with the prediction of the singularity.  Or, in this essay, we assume they definitely will interfere and prevent the singularity because otherwise it leaves us with the complicated questions mentioned above that we are avoiding by Occam's Razor.

Throw a ball, and we can plot a parabola, then extrapolate where the ball will land.  This is analogous to extrapolating that the universe began as a singularity.  However, we are actually throwing a ball toward a wall of fog.  This fog corresponds to the GUT scale, time 0, that we will never have knowledge beyond.  We have no idea what lies in the fog; we have no idea whether the ball will land at the extrapolation of the parabola into the fog.  This essay assumes that something analogous to a bottomless pit exists inside the fog: the ball never lands; the universe has no beginning.

I suppose the more accurate analogy is we see a ball having exited from a foggy area traveling a parabolic path.  From where and how was the ball launched?

In critique of this essay: because we will never be able to test a GUT or TOE, the only way to choose among them seems to be by Occam's Razor again.  Are there simple such theories which permit the GR singularity or something analogous?  There probably are.

[fsnyoxuk] Data horcruxes

1. Start with some data.
2. Cryptographically sign the data.
3. Expand it with an error correcting code.
4. Break it up into pieces, perhaps individual bytes.
5. Choose a nonce, which will be common to all the pieces.
6. Add the nonce to each piece.
7. Add a sequence number to each piece.
8. Cryptographically sign each piece.
9. Expand each piece with another error correcting code.
10. Scatter the pieces.

The data will be difficult to destroy: the data can be reconstructed from a partial collection of partially damaged pieces and verified as authentic.

Kind of a solution in search of a problem.  Previously.  The signature and nonce make the minimum size of a piece annoyingly large.

The total number of pieces needs to be encoded somewhere.  The public key to verify the signatures needs to be stored elsewhere.  Other problems?

[ejwpwgww] Earth as panspermia origin

Large meteorites have hit the earth, creating a splash, launching chunks of earth into space.  Many of those chunks probably had living microorganisms which hitched a ride to whichever next planet that launched chunk of earth then smashed into.

Inspired by Martian meteorites that landed on Earth.

In this way, Earth has probably seeded a large, perhaps cone-shaped, region of the galaxy (or beyond) with life over that past 3 billion years.  Maybe like a contagious constantly traveling constantly sneezing patient zero.  How large is that region?

If there is a habitable planet within that region, what is the probability it escaped infection by Earth?  On one hand, space is big.  On the other hand, there has been a lot of time.  There could also be indirect infections where a planet seeded by Earth thrived, got hit by another meteorite, then chunks of it and its life get launched into space (propagated outbreak in epidemiology).

Of course, one wonders whether Earth itself got seeded from elsewhere.

[bixwyjax] ZPAQ busy beaver

The ZPAQ compressed file format specifies a virtual machine.  This suggests a contest of designing small files which will uncompress (decompress) into large but finite output.

Also, uncompress into interesting output.

[vlvnvito] Monoculture trees

Many famous examples of a disease killing a lot of plants are in agriculture (potato famine) where monoculture likely played a large role in the disease being able successfully infect many plants.

Exceptions seem to include chestnut blight and Dutch elm disease.  Were those trees somehow monocultural also?  What other monoculture trees are there where a disease might quickly kill most of them someday?

[ajwillzv] Pen is mightier than the sword

Substitute the string (without spaces) mightierthanthesword for the word penis in contexts where the latter might be censored.

Ironically, the original aphorism justifies censorship.

[bqbrezti] Is the particle physics desert empty?

The particle physics desert theory states that all fundamental particles have mass less than 1 TeV or greater than 10^13 TeV.

Can this theory be tested without having to test all the way up to 10^13 TeV?  If one has to do that, the theory is useless.  In particular, can the theory be proven correct (a weird thing to do to a theory) by only testing up to 1 TeV?

What is the nature of inflation, neutrino mass, dark matter, and dark energy?  Assuming the desert theory is proven true, will the answers to these questions definitely be found before 1 TeV?  Or, if the answers aren't found, will we definitely know we will not be able know the answers until we can build (at least) GUT-scale particle accelerators?

Of course, astronomers can observe relics from when the universe was at GUT-scale energy to try to answer these questions.

[ariplvdv] GUT and TOE beauty contest

Grand Unified Theories and Theories Of Everything are difficult to test and disprove.  They cannot be tested on current or even reasonably imaginable future particle accelerators.  We can check that a theory agrees with observations in the low-energy regime, and whether they match astronomical observations of faint relics from the universe's high-energy era.

Given these difficulties, selecting a good such theory becomes more of a question of aesthetics than science.  Which such theories are beautiful and which are ugly?  What defines beauty of a theory?  Occam's Razor is likely important.  Given a precise definition of beauty, find, perhaps computationally, the optimally beautiful theory which agrees with weak and faint observations.

The E8 Theory Of Everything likely attracted attention due to its aesthetics.

Tuesday, February 07, 2017

[euzzsqsw] Inflation inside a black hole

Inside a black hole, density and consequently temperature become very high.  At some point of collapse, well inside the event horizon, does the density and temperature resemble the early universe?  Hypothesize inflatons then get produced, causing inflation, a repulsive force which counterbalances gravity and prevents the core from collapsing to a singularity.  This is analogous to the various other processes that counterbalance gravity in normal stars, white dwarves, and neutron stars.

Previously (1) (2) (3)

Inflation seems like an extremely powerful phenomenon based on what it did to the universe.  How much mass would a black hole need to have to overpower inflation?

Philosophically, do we even care what is going on inside an event horizon?

I suppose it matters for black holes with no event horizon, naked singularities, which, if the above hypothesis is correct, won't be singularities, just extremely dense chunks of matter surrounded by very weird spacetime.

[xxmnulmq] Chestnut brain

The inside of chestnuts look strikingly like brains.  What evolutionary fitness function were each tying to optimize that they both converged on the same shape?  Why do chestnuts look the way they do compared to other nuts?  (Possibly centuries of cultivation.)

[cqluwcao] The lighter particle was harder to make

It is curious that the Higgs boson, mass 125 GeV, was finally first seen at the LHC which has 8 TeV (maybe 7) collision energy, whereas the top quark with greater mass 172 GeV was seen earlier at the Tevatron with its only 1.96 TeV collision energy.

Electron-positron colliders tend to be more efficient in terms of converting collision energy into particle mass, but as best as I can tell, neither particle was seen at the LEP which had collision energy 209 GeV.  This might be explained by energy being converted into mass must be produced as matter-antimatter pairs (more generically, some collection that will decay and annihilate back to no mass), so even a perfectly efficient LEP will max out at particle mass 104.5 GeV.

Monday, February 06, 2017

[kxwixtrh] Density of Carmichael numbers

Estimate the number of Carmichael numbers less than x as


Formula (by Erdos, 1956) is from the Wikipedia page.  There is an unknown constant k, which will be discussed later.

The probability that a number is a Carmichael number is p=c(x)/x.  For the generation of a PGP RSA key, we need 4 primes: 2 primes for the master key, 2 primes for the subkey.  The probability that any of the 4 are Carmichael numbers is approximately 4*p (truncating the binomial expansion).  Primes are half the size of the modulus, so the probability of generating a bad key (at least one Carmichael number) is


We explore various values of that unknown constant k.  It turns out the result is quite sensitive to k.  Empirical calculations on the Wikipedia page up to 10^21 (approximately 2^69) suggest k is around 1.86.

If we estimate k=1.8, then we get the following results.  The probability of failure on (absurdly small) 512-bit keys: 3.56e-44 ; 2048-bit keys = 3.63e-159 ; 4096-bit = 3.54e-303 .

If we far more conservatively estimate k=1.0, then 512-bit = 1.35e-24 ; 2048-bit = 1.76e-88 ; 4096-bit = 1.73e-168 .

The probabilities are probably acceptably small to not worry about accidentally encountering a Carmichael number, though you never know about that constant k.  So Fermat tests are fine, no need for the additional complexity of Miller-Rabin.

Friday, February 03, 2017

[zihjrysc] Alpha and Omega

It starts out a children's story, but ends apocalyptic.  Inspired by Harry Potter.  But no one author is skilled at all the styles, so it may be better written collaboratively.

Or, it ends as survival horror.

[vnqzswbf] Ender Purim

Ender spares the life of just one enemy Formic instead of genociding them all.

Saul spares the life of just one enemy Amalekite (Agag) instead of genociding them all as God Commanded.  Haman, a descendant of that survivor, goes on to wage genocidal warfare against the Jews.

Tell a continuation of the Ender saga in which the Formics, descendants of the egg Ender spared, return many generations later and wage genocidal warfare against the humans.  Perhaps with some science fiction time travel (Star Trek: First Contact), that second war is the one Mazer Rackham wins.  Celebrate yearly the anniversary of Rackham's miraculous victory.

Thursday, February 02, 2017

[plwpicim] Direct versus indirect encryption

Direct: Ciphertext encrypted with a key.  Key derived from a password.

Indirect: Ciphertext encrypted with a key X.  Key X is encrypted with a key Y.  Key Y is derived from a password.

There are probably more official names for these.

Indirect encryption allows changing the password without having to reencrypt everything, so seems attractive for things like disk encryption or filesystem encryption.  However, it seems more vulnerable to attack.  If the attackers can get a hold of encrypted X, then they can do a password guessing attack against it, which if successful could be useful even after the user changes their password (changing Y).  What other attacks?  What defenses are there?

Wednesday, February 01, 2017

[dsfjlwim] Transmitting compressed files

A certain absurdity is possible when transferring a file over scp between two filesystems that support transparent compression, e.g., btrfs: File is stored compressed with zlib (other options possible; this is the most absurd).  Uncompressed by a kernel module to make it visible to userspace program.  scp compresses the file with zlib for transmission over the wire.  Receiving scp unconpresses the file, then writes it to the filesystem.  Kernel recompresses the file with zlib to write to the compressed filesystem.

[fmsethjs] High precision UT1

The Earth's rotation is not stable, causing the need for leap seconds.  How precisely is its instability known from moment to moment?

The way to measure it is probably to look at stars with a telescope, noting the time and telescope orientation, though the details of how to do it seem tricky.  Maybe quasars and radio telescopes.

Inversely, how do astronomers keep their telescopes stably pointed at the same location in the sky for long exposure photographs if the earth to which their telescopes are anchored rotates unstably beneath them?

Sit down, then stand up.  Your movement altered the Earth's rotational moment of inertia and consequently its rate of rotation, which in principle could be detected, then maybe the measurement deconvolved to recover your movement.  Anything that involves movement of mass, for example air molecules vibrating in speech, affects the Earth's rotation.  We can imagine a sophisticated surveillance system that monitors actions on Earth by seemingly absurdly observing distant quasars to extremely high precision.

Less ridiculously, the unstable rotation of the Earth could be a source of entropy for a random number generator.  There used to be a random number generator powered by a Lava Lamp.  The Earth is the ultimate Lava Lamp: variations in rotation are caused by movement of magma within the mantle or core.  How many bits per second of entropy can the Earth's rotation produce?

[lrrrishw] Union

The word union could be pronounced onion as if it had the prefix un-.  Onion, then, could be pronounced differently, too.

Tuesday, January 31, 2017

[jniqqxho] Decoupled digital camera

Create a camera whose optics (especially telephoto lens) are not rigidly connected to its display, which might be a smartphone.  Wired or wireless connection.

Inspiration was wanting binoculars to see something far away, but only rarely wanting them.

[isxqeiqb] Formal software engineering

Are formal tools for software development -- proving correctness of code -- needed more for the "make it work right" or the "make it work fast" phase of software development?

[rwkfvqlg] Pythagorean rectangle

The square of the diagonal of a rectangle is equal to the sum of the squares of the sides of a rectangle.

Or, the hypotenuse of a right triangle is equal to the sum of the squares of the two legs.

The former seems a less imposing (less jargon filled) way of introducing the Pythagorean theorem.

[cldreftj] Bottom class not assimilating

In some societies, we observe a seeming paradox: a bottom social class refusing to assimilate, refusing to give up the social markers that identify them as part of the bottom class, markers by which they then get discriminated.  Possible explanations:

The paradox is an illusion.  We only notice the few unusual outliers of those refusing to assimilate.

Assimilation takes generations due to the time constant of psychological identity.

Maintaining the social markers buys into a social safety net within the community of that class, which is more valuable than the risky benefits of assimilation.  They are making a rational decision.

The opportunities for assimilation are actually illusions.  No amount of dropping social markers will disconnect you from your social class, because the upper classes want to keep the lower classes well populated.

[vpswchba] Human rights abuses are inevitable with globalization

Hypothesize that with globalization, human rights abuses or more generally governments or societies treating (at least some of) their citizens terribly, or allowing them to be treated terribly, are inevitable.  This is a consequence of the combination of one economic, one political, and one psychological effect.

The economic effect is that a society/government which exploits its population for labor at low wages will "win" in a globalized economy.  The world market sets the price of goods.  If one country refuses to exploit -- perhaps instead setting a minimum wage or providing social services to its population, then another country will exploit, not doing those things.

The political effect is that laws end at country borders.  One country might decide exploitative labor conditions are bad and outlaw them, but they can't force another country to do the same. (Or maybe they can, with military meddling and cross-border propaganda, most famously the Communist movement.)  Even those being exploited may wish to maintain the status quo.

The psychological effect is that people can survive, thrive, and even feel satisfied and happy in very bad conditions.  (We still need to understand when, why, and how.  Previously somewhat related.)

If this hypothesis is true, then it is dismal science, reminiscent of Malthus.  It will always be a race to the bottom.

Perhaps then blame globalization: globalization is free (or freer) trade agreements, low cost international shipping (perhaps results of technology and world peace on the high seas -- few pirates).

[gbupycok] Classical to quantum game

Create a game which starts out obeying the laws of classical physics, but as the levels get harder, more and more quantum mechanics effects occur.  Perhaps the story is that the scale gets smaller or the temperatures get colder.

Quantum tunneling to get through classically impenetrable barriers.

Ends with the player being able to intuitively think quantumly.

Monday, January 30, 2017

[tdoyjpic] Testing the Collatz conjecture on 10-million-bit numbers

tl;dr: No counterexamples to the Collatz conjecture were found.

Assume the Collatz conjecture is false; that is, there exist starting numbers which do not end in the 4-2-1 cycle.

Further major assumption: these counterexamples become much more numerous for larger integers; the reason the Collatz conjecture has seemed true in the range that it has been verified so far is because of the Strong Law of Small Numbers.

Then, we might be able to find counterexamples simply by testing some random large starting numbers.  One problem: when testing a number, how can one tell if it is a counterexample, not headed to a 4-2-1 cycle?  How can one tell if one has iterated enough?

Simple practical solution: start by testing small random numbers and gradually increase the size.  The smaller numbers will all reach 4-2-1, and the number of iterations and computation time can be recorded for each of them.  As the numbers get larger, the number of iterations and computation time will increase sort of smoothly.  If we encounter a number which is taking much longer than the extrapolation of the trend seen thus far, then we know something weird is going on with it.

We tested random starting numbers as large as 10313058 bits, the last one taking 74494956 iterations over 12 hours of computing time (though it was not very optimized code).  Every number tested converged to 4-2-1.

Source code in Haskell and logs.

We wish we had SIMD accelerated (e.g., GPU) small*large arbitrary precision multiplication (previously mentioned) to compute 3*x for large x.  x/2 could also be accelerated with SIMD.  x+1 will only astronomically rarely overflow the least significant limb.

Previous similar attempt, which was much slower because then large integers were represented as lists of Bool.

Wednesday, January 25, 2017

[khvlvecm] Simplified syllables

10 initial consonants: (null) m p b t d s z k g

5 vowels: i e a o u

2 ending consonants: (null) n

Nice round 100 though that was not intentional.

A little bit awkward for English spelling because g changing its sound before i and e.  t d s z change their sound in Japanese depending on the vowel.

Tuesday, January 24, 2017

[zghmwfxn] Carlsen - Karjakin final mating combination

We analyze the variations after 49.Rc8+ all the way to checkmate.  Moves that are the only moves which preserve the win are marked with a single exclamation point.  If there are multiple winning moves tied with the same shortest distance to checkmate, then all are given (which is unconventional for analysis).  We also give all black defenses, even if they get checkmated quicker.  The two variations with 54.Qd5+ cause checkmate 1 move slower so are marked with a question mark.

[Event "Carlsen - Karjakin World Championship"]
[Date "2016.11.30"]
[Round "13.4"]
[White "Magnus Carlsen"]
[Black "Sergey Karjakin"]
[Result "1-0"]
[ECO "B54"]
[EventDate "2016.11.30"]

1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.f3 e5 6.Nb3 Be7 7.c4 a5 8.Be3 a4 9.Nc1 O-O 10.Nc3 Qa5 11.Qd2 Na6 12.Be2 Nc5 13.O-O Bd7 14.Rb1 Rfc8 15.b4 axb3 16.axb3 Qd8 17.Nd3 Ne6 18.Nb4 Bc6 19.Rfd1 h5 20.Bf1 h4 21.Qf2 Nd7 22.g3 Ra3 23.Bh3 Rca8 24.Nc2 R3a6 25.Nb4 Ra5 26.Nc2 b6 27.Rd2 Qc7 28.Rbd1 Bf8 29.gxh4 Nf4 30.Bxf4 exf4 31.Bxd7 Qxd7 32.Nb4 Ra3 33.Nxc6 Qxc6 34.Nb5 Rxb3 35.Nd4 Qxc4 36.Nxb3 Qxb3 37.Qe2 Be7 38.Kg2 Qe6 39.h5 Ra3 40.Rd3 Ra2 41.R3d2 Ra3 42.Rd3 Ra7 43.Rd5 Rc7 44.Qd2 Qf6 45.Rf5 Qh4 46.Rc1 Ra7 47.Qxf4 Ra2+ 48.Kh1 Qf2? {allows the mating attack} 49.Rc8+!! {not the only move that wins, but the fastest and of course prettiest} Kh7 ( 49...Bd8 50.Rxd8+! Kh7 51.Qh6+! Kxh6 ( 51...gxh6 52.Rxf7#! ) 52.Rh8#! ) ( 49...Bf8 50.Rxf8+! Kxf8 ( 50...Kh7 51.Qh6+! Kxh6 ( 51...gxh6 52.R5xf7# ) 52.Rh8#! ) 51.Rxf7+! Ke8 ( 51...Kg8 52.Rf8+! Kh7 53.Qf5+! Kh6 ( 53...g6 54.Qxg6# ) 54.Rh8# ( 54.Qg6# ) ) 52.Rf8+! Kd7 ( 52...Ke7 53.Qf7# ) 53.Qf5+ ( 53.Qf7+ Kc6 54.Rc8+ ( 54.Qd5+? Kc7 ( 54...Kd7 55.Qb7+ ( 55.Rf7+ Kc8 ( 55...Kd8 56.Qxd6+ Ke8 ( 56...Kc8 57.Qc7# ( 57.Qf8# ) ) ) ( 55...Ke8 56.Qe6+! Kd8 57.Qd7# ) 56.Qb7+ ( 56.Qc6+ Kb8 ( 56...Kd8 57.Qd7# ) 57.Qb7# ( 57.Qe8# ) ) ( 56.Qe6+ Kb8 ( 56...Kd8 57.Qd7# ) 57.Qe8# ) 56...Kd8 57.Rf8# ( 57.Qd7# ) ( 57.Qb8# ) ) ( 55.Qb5+ Kc7 ( 55...Ke7 ( 55...Ke6 56.Qe8# ) 56.Qe8# ) 56.Rf7+ Kb8 ( 56...Kc8 ( 56...Kd8 57.Qd7# ) 57.Qe8# ) 57.Qe8# ) 55...Ke6 56.Re8+ ( 56.Qf7+ Ke5 57.Qd5# ) 56...Kf6 57.Qe7# ) 55.Rf7+ Kd8 ( 55...Kb8 56.Qb7# ) ( 55...Kc8 56.Qb7+ Kd8 57.Rf8# ( 57.Qd7# ) ( 57.Qb8# ) ) 56.Qxd6+ Ke8 ( 56...Kc8 57.Qc7# ( 57.Qf8# ) ) 57.Rf8# ( 57.Qd7# ) ( 57.Qe7# ) ) 54...Kb5 55.Qc4+ Ka5 56.Ra8# {Longest defense} ) 53...Kc6 ( 53...Ke7 54.Qf7# ) ( 53...Kc7 54.Qc8# ) 54.Rc8+ ( 54.Qd5+? Kc7 ( 54...Kd7 55.Rf7+ ( 55.Qb7+ Ke6 56.Re8+ ( 56.Qf7+ Ke5 57.Qd5# ) 56...Kf6 57.Qe7# ) ( 55.Qb5+ Kc7 ( 55...Ke6 56.Qe8# ) ( 55...Ke7 56.Qe8# ) 56.Rf7+ Kd8 ( 56...Kb8 57.Qe8# ) ( 56...Kc8 57.Qe8# ) 57.Qd7# ) 55...Kc8 ( 55...Kd8 56.Qxd6+ Kc8 ( 56...Ke8 57.Rf8# ( 57.Qd7# ) ( 57.Qe7# ) ( 57.Qf8# ) ) 57.Qc7# ( 57.Qf8# ) ) ( 55...Ke8 56.Qe6+! Kd8 57.Qd7# ) 56.Qc6+ ( 56.Qe6+ Kd8 ( 56...Kb8 57.Qe8# ) 57.Qd7# ) ( 56.Qb7+ Kd8 57.Rf8# ( 57.Qd7# ) ( 57.Qb8# ) ) 56...Kb8 ( 56...Kd8 57.Qd7# ) 57.Qb7# ( 57.Qe8# ) ) 55.Rf7+ Kc8 ( 55...Kd8 56.Qxd6+ Ke8 ( 56...Kc8 57.Qc7# ( 57.Qf8# ) ) 57.Qe7# ( 57.Rf8# ) ( 57.Qd7# ) ( 57.Qf8# ) ) ( 55...Kb8 56.Qb7# ) 56.Qc6+ Kd8 57.Qd7# ) 54...Kb7 55.Qd7+! Ka6 56.Ra8#! {Longest defense} ) 50.Qh6+! ( 50.Qh6+ Kxh6 ( 50...gxh6 51.Rxf7#! ) 51.Rh8#! ) 1-0

It surprised me that Carlsen worked out that 49...Bf8 is mate, even though it is quite long.  In the Longest defense variations, the black king gets chased all the way to the A file.  However, the variations with 54.Qd5? have that as a more natural move, boxing in the black king, and many end with a more natural back rank mate.

Also a bit surprising that Karjakin did not play 49...Bf8.

Create a tool to produce analyses like this, with a UI to navigate variations including doing something efficient with transpositions.

[xhkgvkxz] Ticking of several imperfect clocks

Place multiple clocks ticking seconds near each other.  If they are not in sync, the ticks with repeat a rhythm.  If they are imperfect, the rhythm will change over time.

[tokcyiph] Civil service hierarchy

Presidents are selected from state governors.  Governors are selected from mayors and city managers of large cities.  They then from small cities.

Similarly several levels of legislatures and legislators.

Similarly several levels of judges.

All this is already done mostly informally.  New wrinkle: each level periodically shuffles its members, e.g., governors move to governing a different state.  This demonstrates how they perform under broadly varied conditions, useful information when selecting for the next higher level up the hierarchy.

Flaws in the system:

Only the president ever deals with military, monetary policy, international diplomacy.

Local people might not be lead or represented by one of their own, if things keep getting shuffled.  Maybe apply only to the executive and judicial branches.

Is corruption worse under this system?

By requiring candidates for a higher post all to have experience at a lower post, it allows comparing ability: who did better governing (say) a poor state?  Judging by ability is fine, but then where and how does politics -- differences in opinion -- enter?  (It will inevitably do so.  Perhaps corruption.)  It would be nice if the legislature could be kept the only political branch of government, but seems unlikely.

Political enemies might try to make go poorly governor's term (hurting the residents in the process) for the larger prize of derailing that person's chances at presidency.

Being effective at a certain level of the hierarchy might require a lifetime to learn.  There aren't enough lifetimes to learn the next level.

What are the required qualifications for Vice President?  Maybe Lt. Governor.  Then, we assume vice-presidency qualifies you for presidency.

[lsftlwrt] Eliminating mind-control microorganisms

There are microorganisms which do mind control on humans, famously Toxoplasma.  In the near future, I predict we will discover many more of them, catalogue them, measure their prevalence, and eliminate them using public health techniques.

Humanity might then see a new age in which a vast mental fog has gotten lifted.

But what if it was a microorganism infection in the population that helped someone achieve or maintain power?  Would they be keen to deploy public health techniques to eliminate that microorganism?

What if it is a microorganism that is helping prevent anarchy?  Perhaps encouraging people to be docile, or not to fight each other, or form social connections evolutionarily advantageous for the microorganism to propagate?

[jlrxidcc] Lentils around an air bubble

Observed in water a few dry lentils clustered around an air bubble, sticking to it by surface tension.  The cluster was heavier than water.  Observed multiple such clusters. The air bubbles wer probably from aerated water poured on the dry lentils in a pot.

Monday, January 23, 2017

[hkmdbtur] Boston forgives

The concept of forgiveness -- especially the inability to do so -- often reveals the hate or contempt that was there all along, perhaps previously concealed by political correctness.

Inspired by a Boston Forgives T-shirt, in response to the militaristic and Islamophobic Boston Strong.

[pbgsqvlp] Maximizing golf

Hit the ball as far as possible, modifying the ball and bat and tee as much as wanted (ball must remain spherical; human power only).  Baseball, tennis, jai alai.  Probably a sling launching a small dense ball will be the max.  Previously, throwing a projectile without a launching tool.

Probably need to disqualify building a trebuchet with weight lifted by human power.

[vjcpssrm] Notes on installing Ubuntu 16.04 to a USB stick

Created Ubuntu 16.04 amd64 server installer image on a USB stick with unetbootin.  This resulted in ominous warning message on boot saying things might go wrong if one uses unetbootin.  The warning is probably due to or the Ubuntu equivalent.

Retried creating using Ubuntu's official tool, usb-creator-gtk.  This results in "gfxboot.c32: not a COM32R Image" . Workaround described at , i.e., type help and press enter.

The underlying problem with the unetbootin route appears to be Debian/Ubuntu's fault; the filenames have length longer than 64 characters in length, violating the Joliet file system standard.

Used mkusb, which requires a ppa:
sudo add-apt-repository ppa:mkusb/ppa

On a Dell optiplex, the key to trigger boot options is F12.

First interesting experiment was to try to install everything inside LVM, without /boot as a separate partition outside of LVM.  It used to be one needed /boot outside of LVM, but nowadays grub has an lvm module.  I've been bitten too many times by a too small /boot partition filling up with too many old kernels, so we'd like to avoid a separate /boot partition.  Let's see if it works.

All these experiments were done by installing Ubuntu onto a 4GB USB key, a somewhat unusual install target (and as mentioned above, from USB key as well).

From experience, choose en_US.UTF-8 locale, not C, because desktop environments fail when there is only a C locale, e.g., terminal programs don't start.

(Experience was, almost no application starts.  uxterm worked.  Trying to start gnome-terminal from inside uxterm gives
Error constructing proxy for org.gnome.Terminal:/org/gnome/Terminal/Factory0: Error calling StartServiceByName for org.gnome.terminal: GDBus.Error:org.freedesktop.DBus.Error.Spawn.ChildExited: Process org.gnome.Terminal exited with status 8

Select noatime as a filesystem mount option because USB SSD has limited writes.

Things went smoothly until the grub install step.  Choosing any of the disks resulted in an error, e.g., "unable to install grub in /dev/mapper".  One needed to manually specify /dev/sdb . To know for sure what disk is being installed, get a shell (ctrl-alt-f2) and do pvdisplay.

After install, this much space was used: (1K blocks)
/dev/mapper/vg--one-root 3800784 total 1371468 used 2216532 available

Here are the autogenerated grub.cfg and fstab.

The next adventure was to repeat the same idea, but all of LVM inside an LUKS/dm-crypt encrypted container.

Created the dm-crypt container with System Rescue CD, because I wanted to customize the number of rounds of password hashing.  ArchWiki is pretty good:

system rescue cd 4.7.3, with docache is nice.

During Ubuntu install, Grub install failed.  Looking at the logs (ctrl-alt-F4) found:

grub-install: error: attempt to install to encrypted disk without cryptodisk enabled.  Set GRUB_ENABLE_CRYPTODISK=1

Workaround for this involved getting a shell (ctrl-alt-f2), editing /target/etc/default/grub in the installed system to have GRUB_ENABLE_CRYPTODISK=y . We do "y" and not "1" as the error message states, because which has not been fixed in this version of Ubuntu.

Use nano as the available editor in the install shell.

After grub, install completes successfully.  Here are the autogenerated grub.cfg and fstab.

Booting requires typing the disk unlock password twice, once for grub, then again for kernel filesystem mount.  The amount of time it takes to verify a password differs greatly between them.

Aside: describes how to only need to type the password once, into grub.  grub then finds a keyfile on the unlocked disk and passes it to the kernel.  I did not try this hack.

Typing password twice is fine for now.  The grub password prompt, in contrast to the kernel password prompt, does not display a text cursor, so one cannot obviously see if one's keyboard is working properly.  Hitting Enter after typing the password does not advance a visible cursor to the next line.

Ran tasksel to install "Xubuntu minimal".  Also installed firefox.  Also did aptitude full-upgrade, installed a new kernel.  The new kernel did successfully boot, so the necessary grub magic with LUKS and dm-crypt just worked.

During and after full-upgrade, there is a persistent error on both shutdown and boot about lxd-containers.service.  The workaround is to just once manually restart lxd and reboot.

sudo service lxd restart

After removing the old kernel, total 1k blocks used according to df is 2751788, or 77% of the 4 GB drive.  Peak usage was 93% during the upgrade.

Xubuntu does provide the Guest login account.

Next experiment, same but install "Lubuntu minimal".  Lubuntu is lighter than Xubuntu.  After similar install, 2459872 K used, 69%

Next experiment, try btrfs because it has transparent compression.  All these experiments were done on a slightly different USB stick, so unfortunately cannot compare with previous experiments.

Sandisk Cruzer Fit is a compact USB stick that does not stick out very much from the USB port.

Setting btrfs compression is done at mount, not at filesystem creation.  We use Ubuntu Expert Mode (f6 "Other Options" at the boot screen) in order to have pauses between steps.

Creating an encrypted container, then directly creating btrfs inside the encrypted container fails. Red screen "Encryption configuration failure" "You have selected the root file system to be stored on an encrypted partition.  This feature requires a separate /boot partition on which the kernel and initrd can be stored." "You should go back and setup a /boot partition".

Workaround: btrfs inside of LVM inside of encrypted container.

noatime is available as an option in the installer UI.

Expert Mode allows a pause between "Partition disks" and "Install the system".  Get a shell, then 'mount -o remount,compress=lzo,ssd /target'.  /target/home automatically remounts to pick up compress=lzo, according to mount.

Where it asks, choose a generic kernel and a big initrd with "everything" because the usb key might be used to boot a different computer.

System Rescue CD seemed to have problems unmounting LVM on shutdown.  Use vgchange -an and lvchange -an .

Chose to install grub to the EFI removable media path

Edited /target/etc/fstab to have compress=lzo as options.  Also ssd option.

In retrospect, encrypted home directory and filesystem compression don't work so well.  ecryptfs does not have compression , marked "Won't fix".  Read about CRIME and BREACH exploits against compress-then-encrypt.

Mistyping the disk encryption password into grub results does not result in a prompt to try again, instead a grub shell.  Reboot to try again.

Usually avoid recommended packages, especially on this limited disk system.  But xul-ext-ubufox seems like a good recommended package to install.

All the extra package installs were done in console (Ctrl-Alt-F1) to avoid disk space usage of starting X (window manager caches, initial config, etc).

after lubuntu, full-upgrade, firefox, xul-ext-ubufox on compress=lzo:
3903488 1K total, 2573916 used, 917156 available, 74%
after reboot
3903488 2545980 944868 73% (slight improvement)

which is higher than the 69% on a different disk

Plan is to add an additional usb stick if we need swap.

Unlocking the disk in grub 15.75 sec.  Later during Linux boot, unlocking the same disk on the same computer takes 6.68 sec.  Grub is clearly not using the most efficient password hashing code.

cryptsetup -i 20000 causes grub 26 seconds, linux 11 seconds.

btrfs: ubuntu creates @ and @home subvolumes automatically.

Instead of editing /etc/default/grub directly, let's try putting GRUB_ENABLE_CRYPTODISK=y in /etc/default/grub.d (not to be confused with /etc/grub.d).  It needs to be a file with extension .cfg . (the bug also complains about lack of documentation)  /usr/sbin/grub-mkconfig is the script that reads these files.

dmesg log, both in boot and during full-upgrade
BTRFS error (device dm-1): could not find root 8

aptitude full-upgrade took 40 minutes

during aptitude purge old linux image
File descriptor 4 (/) leaked on vgs invocation. Parent PID 5071: grub-probe

tasksel lubuntu minimal took 194 minutes.

after firefox and xul-ext-ubufox
3903488 2532984 951304 73%

which provides about 7MB more than lzo, but very small improvment, which is strange.

/usr/lib is 570 MB, and gzip -v reports 61.2% compression as a tar.

btrfs mount option compress-force=zlib: df says "3903488 2461512 1025048 71%", so not much of an improvement.

weird issue on console that the cursor jumps to column 1 after about a minute after boot.

Remove old linux kernel and linux-headers to save space
sudo aptitude purge linux-headers-4.4.0-21
which removes the generic package as a reverse dependency.

2298488 1143560 67%

Tuesday, January 17, 2017

[jaoosiou] How weird is your secret key?

Create a tool that will analyze the primes of your RSA secret key (private key): count the number of consecutive composites before and after each prime, and report how unusual (perhaps a p-value) that count is compared to what one would expect by the Poisson distribution and Prime Number Theorem.  This should be easy.

If primes were found by testing consecutive numbers (e.g., GnuPG) then these numbers will be aberrantly high.

[tadwseml] King swipe

Given a rectangular grid of points, draw a directed line segment from a point to an orthogonal or diagonal neighbor (one chess king move away).  How many possible line segments are there?

f(x,y)=2*(4*x*y - 3(x+y) + 2)
? f(3,3)
? f(3,4)
? f(3,5)
? f(3,6)
? f(4,4)
? f(4,5)
? f(4,6)

This provides a large number of simple input gestures for a touchscreen keyboard.  Every gesture is local, so it is easy to have explanatory annotations.

Other grids possible: consider 12 directions on a hexagonal grid.

Sunday, January 15, 2017

[ukjhypur] Shot put with running start

Shotput is an elegantly simple sport: throw the sphere as far as possible.

Consider lifting restrictions to make the sport simpler: the thrower does not need to stay inside the throwing circle but need only stay behind a line.  The thrower may use a running start.  This would make it a little like bowling.  Somewhat more complicated is to have a pool of water or sand pit in front of the line: the thrower is permitted to fall in the water or sand after throwing, so can be running at maximum speed at the point of release right at the line.  How would throwing technique change?

Apply similar anarchy to javelin: instead of a sphere, throwers are permitted to choose any shape of at least the specified weight.  If technology improves so that throwers are throwing too far (as has already occurred once in javelin), increase the minimum weight.  We probably need rules to forbid, for example, powered flight.  I suspect the best shape might resemble an Aerobee.

There will be a frontier of records of weight versus distance.

Friday, January 13, 2017

[kemfqqdz] Magnetic levitation

There are two major types of magnetic levitation for trains.

Electromagnetic levitation: German Transrapid, Shanghai Maglev.

Electrodynamic suspension: two subtypes.

With superconductors, relying on diamagnetism: JR Maglev

Without superconductors, relying on ferromagnetism: Inductrack, Hyperloop.

It is very surprising that the superconductor subtype was developed (to a working full-scale prototype) before the non-superconductor version.  Superconducting magnets seem much more expensive and difficult.

[bwootzwo] Minesweeper scratch ticket

Minesweeper is the best puzzle to be made in physical form in the style of a scratch ticket.  (Not good for the actual lottery; people will repaint incorrectly scratched mines if money is riding on it.)  Perhaps it can be included as a fun irrelevant puzzle in lottery tickets.

What other puzzles would work?

Sudoku as scratch ticket might be a good way to temporarily conceal then deliver the solution.  It could include "mines" of squares that are not solvable by logic, though that might be a tricky thing to define.  Perhaps a sudoku that does not have a unique solution.

[xjujmpsg] Randomly discarding most odd numbers being tested for primality

The common but bad algorithm to find a random large prime number (e.g., for RSA) is first to generate a large number x, then test in order x, x+1, x+2,... until a prime is found.  This is bad because it is not uniform: it will preferentially select primes with large prime gaps preceding them.  We do not know yet if this bias causes significant cryptographic weakness.  GnuPG uses this algorithm, as of 1.4.21.

The right way to fix this is to generate complete new random numbers for each number tested for primality.  However, this consumes a lot of entropy.

We can partially repair the problem as follows: test numbers in order starting from x as before.  However, before testing a number for primality, reject it outright with high probability, perhaps 0.999.  Then, only 0.1% of numbers will be tested for primality, which will skip over many actual primes, so avoid many starting x's mapping to the same found prime x+i.

The pseudorandom number generator used for sampling the 0.1% probably does not have to be very good, so it can be quick, so very little computing time will be spent rejecting numbers.  Most of the computing time will be primality testing.

How good is this repair?  How strong does the sampling PRNG need to be?  Does it need to be cryptographically strong?

Another way to do it might be to select a large random-sized jump to each new number to be tested.

[ntmxyalx] Least common multiple of the first N integers

We give the size of the number in bits, so logarithm base 2 of OEIS A003418 Previously.

p=1 ; for(i=1 , 733 , p=lcm(i , p) ; printf("%d %d ; " , i , floor(log(p) / log(2))))

Omitting repeated values for compactness (log of A051451):

p=1 ; for(i=1 , 733 , g=gcd(i,p) ; if(g!=i , p=p*i/g ; printf("%d %d ; " , i , floor(log(p) / log(2)))))

2 1 ; 3 2 ; 4 3 ; 5 5 ; 7 8 ; 8 9 ; 9 11 ; 11 14 ; 13 18 ; 16 19 ; 17 23 ; 19 27 ; 23 32 ; 25 34 ; 27 36 ; 29 41 ; 31 46 ; 32 47 ; 37 52 ; 41 57 ; 43 63 ; 47 68 ; 49 71 ; 53 77 ; 59 83 ; 61 88 ; 64 89 ; 67 95 ; 71 102 ; 73 108 ; 79 114 ; 81 116 ; 83 122 ; 89 129 ; 97 135 ; 101 142 ; 103 149 ; 107 155 ; 109 162 ; 113 169 ; 121 172 ; 125 175 ; 127 182 ; 128 183 ; 131 190 ; 137 197 ; 139 204 ; 149 211 ; 151 218 ; 157 226 ; 163 233 ; 167 240 ; 169 244 ; 173 251 ; 179 259 ; 181 266 ; 191 274 ; 193 282 ; 197 289 ; 199 297 ; 211 305 ; 223 312 ; 227 320 ; 229 328 ; 233 336 ; 239 344 ; 241 352 ; 243 353 ; 251 361 ; 256 362 ; 257 370 ; 263 378 ; 269 386 ; 271 395 ; 277 403 ; 281 411 ; 283 419 ; 289 423 ; 293 431 ; 307 439 ; 311 448 ; 313 456 ; 317 464 ; 331 473 ; 337 481 ; 343 484 ; 347 492 ; 349 501 ; 353 509 ; 359 518 ; 361 522 ; 367 531 ; 373 539 ; 379 548 ; 383 556 ; 389 565 ; 397 573 ; 401 582 ; 409 591 ; 419 599 ; 421 608 ; 431 617 ; 433 626 ; 439 634 ; 443 643 ; 449 652 ; 457 661 ; 461 670 ; 463 679 ; 467 687 ; 479 696 ; 487 705 ; 491 714 ; 499 723 ; 503 732 ; 509 741 ; 512 742 ; 521 751 ; 523 760 ; 529 765 ; 541 774 ; 547 783 ; 557 792 ; 563 801 ; 569 810 ; 571 820 ; 577 829 ; 587 838 ; 593 847 ; 599 856 ; 601 866 ; 607 875 ; 613 884 ; 617 893 ; 619 903 ; 625 905 ; 631 914 ; 641 924 ; 643 933 ; 647 942 ; 653 952 ; 659 961 ; 661 970 ; 673 980 ; 677 989 ; 683 999 ; 691 1008 ; 701 1017 ; 709 1027 ; 719 1036 ; 727 1046 ; 729 1047 ; 733 1057 ;

[nqxjypxr] Tunable urandom

On Linux, /dev/random blocks when high quality random bits are not available, but /dev/urandom continues to emit "only cryptographically strong" bits even if it hasn't been able to mix in entropy for a long time.

Wanted is something tunable in between: it blocks when the ratio of entropy in and bits out decreases below some user-specified threshold.

[dvaklhhl] Falsify the present

Trollishly create false records of the present, your present, so that future researchers and historians will puzzle over them or perhaps blindly accept them as truth.

Falsifying the present seems easier than falsifying the past, because the past requires access to historical records.

What kinds of false records will the future be most likely to be gullible to?  Perhaps ask current historians what types of records of the past they struggle to find or verify.

Coming soon will be significant climate change.  Record what life is like before climate change.

Tuesday, January 10, 2017

[sxisqanh] Is it live or is it Memorex?

Under what conditions is it preferable to consume or experience and event live instead of a sound or video recording?

The biggest difference of "live" is that it is social: you consume simultaneously with others around you.  When does that matter?  How does that matter? 

There are a few other technical differences that are rapidly being eliminated by technology, e.g., VR.

[fcpxjrfj] Opposition to death penalty

There are those who oppose the death penalty because it is too cruel.  There are others who oppose it because it is not cruel enough: lifetime imprisonment is believed crueler so better -- we have a very vindictive society.

In places which have abolished the death penalty, how much was the reason for abolishing it the latter reason?

Those who believe prison should be cruel provide the political force for mistreatment of prisoners by guards or by fellow inmates.  Stand idly by and let it happen.

[lavljmgv] Fixing leap seconds

The obvious solution to avoid time going backward at the leap second is to deploy a separate time standard which monotonically counts forward, so it is TAI except expressed as a number.  We will need a new set of system calls to get and set that number.  We probably need to augment NTP to distribute that number. 

Computers can internally count the new number, or internally count UTC as they currently do.  They can provide both system calls, converting between them depending on which system call is invoked and what they internally count.  New and updated software should use the new system call, but the old system call can be provided indefinitely for backward compatibility.  New systems should internally count the new number.

Smearing the leap second over (say) a day is less than ideal because time will disagree with computers not smearing.  It may also interfere with tasks needing a time interval to high precision.

The new number should be significantly different from the POSIX counter (Unix time) so that if one is accidentally substituted for the other, it will be obvious.  Previously, we proposed a fanciful 835-bit wide number, which avoids needing to encode floating point and will probably never need to worry about overflow.

There is something wrong about attempting to politically end leap seconds when this kind of non-disruptive software solution exists.

[wvrnupbd] Rogue planets

During the formation of a solar system, there are lots of planets which haven't organized themselves into stable orbits yet, so many planets probably get ejected.

At the end of its lifetime, a star undergoes mass loss which probably destabilizes planetary orbits (e.g., by breaking resonance structures) causing more planets to become ejected.

How dense is space with planets unattached to stars?  Also comets, of course.  Navigation hazard?

[qgppohzt] Brotli text generator

Invert the language model hardcoded into the Brotli compression algorithm to turn it into a random text generator.

Monday, January 09, 2017

[lvbetgkb] Right section of a function

A left section of a binary (two-argument) function is easy to write in Haskell using partial function application: just omit the last (right) argument.  A right section is a little bit more awkward, requiring backquotes, lambda, or flip.

import Data.Function((&));

-- example binary function (not an operator)
f2 :: a -> [a] -> [a];
f2 = (:);

-- we will use the larger functions later
f3 :: Int -> a -> [a] -> [a];
f3 _ = (:);

f4 :: Bool -> Int -> a -> [a] -> [a];
f4 _ _ = (:);

test :: [String];
test = map (\f -> f 'h') -- all of these evaluate 'h':("el"++"lo") yielding hello
[ (`f2` ("el" ++ "lo")) -- backquotes (grave accents) are inline operator syntax. An inline operator followed by an argument, all surrounded by parentheses, is operator right section syntax: one is supposed to imagine a hole in front of the backquotes: (__ `f2` ("el" ++ "lo"))
, (\arg1 -> f2 arg1 ("el" ++ "lo")) -- lambda syntax
, (\arg1 -> f2 arg1 $ "el" ++ "lo")
, ((flip f2) ("el" ++ "lo"))
, ((flip f2) $ "el" ++ "lo")
, (flip f2 $ "el" ++ "lo")
, (flip f2 ("el" ++ "lo")) -- It might be a little surprising that this one works, if one had thought of "flip" as a function taking only one argument, namely the function to be flipped. However, because of currying, it actually takes 3 arguments. flip :: (a -> b -> c) -> b -> a -> c.
, ("el" ++ "lo" & flip f2)

-- For these 3- and 4-argument cases, we would like to create a lambda on the penultimate argument.
-- , (`f3 (2 + 3)` ("el" ++ "lo")) -- This does not work because the contents of the backquotes must be a binary function that is a single token, not an expression.
, (let { t2 = f3 (2 + 3) } in (`t2` ("el" ++ "lo")))
, (\penultimate -> f3 (2 + 3) penultimate ("el" ++ "lo"))
, (\penultimate -> f3 (2 + 3) penultimate $ "el" ++ "lo") -- this wordy lambda syntax is one of the best in terms of low parenthesis count and avoiding deep parentheses nesting.
, (flip (f3 (2 + 3)) ("el" ++ "lo")) -- similar to "a little surprising" above
, (flip (f3 (2 + 3)) $ "el" ++ "lo")
, (flip (f3 $ 2 + 3) $ "el" ++ "lo")
, ((flip $ f3 (2 + 3)) $ "el" ++ "lo")
, ((flip $ f3 $ 2 + 3) $ "el" ++ "lo")
, ("el" ++ "lo" & (f3 (2 + 3) & flip))
, ("el" ++ "lo" & (2 + 3 & f3 & flip))

, (\penultimate -> f4 (not True) (2 + 3) penultimate ("el" ++ "lo"))
, (\penultimate -> f4 (not True) (2 + 3) penultimate $ "el" ++ "lo")
, (let { t2 = f4 (not True) (2 + 3) } in (`t2` ("el" ++ "lo")))
, (flip (f4 (not True) (2 + 3)) ("el" ++ "lo"))
, (flip (f4 (not True) (2 + 3)) $ "el" ++ "lo")
, ((flip $ f4 (not True) (2 + 3)) $ "el" ++ "lo")
, ((flip $ f4 (not True) $ 2 + 3) $ "el" ++ "lo")
, ("el" ++ "lo" & (f4 (not True) (2 + 3) & flip))
, ("el" ++ "lo" & (2 + 3 & f4 (not True) & flip))
, ("el" ++ "lo" & (2 + 3 & (not True & f4) & flip))

(\f -> f 'h') could have been written ($ 'h') , a right section itself, but we deliberately avoid being potentially obscure in the test harness.

Friday, January 06, 2017

[kzpybzhu] Paragraph separators in Gmail android app

Write two paragraphs of text as a message on different phones and examine the HTML that actually gets sent.  (Easiest done at the receiving end.). There is something terribly wrong with how the newer Nexus 5x does it.

This affects blog-by-email for this blog, and makes GnuPG unable to parse PGP ASCII armor.

<div dir="auto">Nexus<div dir="auto"><br>
</div><div dir="auto">5x</div></div> 

Android version: 7.0
Android security patch level: November 5, 2016
Baseband version: M8994F-
Kernel version: 3.10.73-g5a3d8a9
Build number: N5D91L


Google Keyboard

<p dir="ltr">Galaxy</p>  <p dir="ltr">Nexus</p> 

Android version 4.2.2
Baseband version I515.10 V.FK01 / I515.FK02
Kernel version 3.0.31-g9f818de
Build number JDQ39


Google Keyboard

[jardjvop] More bagpipe

Take the principle of a bagpipe, air supplied by mouth but pressure supplied by arm, and create other wind instruments, probably louder than current versions with pressure supplied by mouth and lungs.

Unfortunately it will probably lose the great facility of embouchure.

[rfwkfqbs] No duals

Test whether the solution to a mate in N chess problem has no duals.  I think this means, on every path of most resistance (there may be multiple such paths because the defender could defend multiple ways) the attacker has a unique move to complete mate in N.  If the defender makes suboptimal moves, then the attacker's best moves need not be unique.

Perhaps relax the constraint toward the end when it is mate in 1 or 2.  Or some sort of clearly winning position in a "play and win" problem.

Wednesday, January 04, 2017

[oqgqulke] Capitalized punctuation

Capitalize `{|}~ to get @[\]^ according to the ASCII table (alter 1 bit).  DEL maps to _

Apply a similar transformation to the digits 1..9 to get !"#$%&'() and 0 maps to space.  This is almost, but not quite, the shifted numerals on the keyboard.  Beyond 9, we also have :;<=>? shiftable to *+,-./

Shift the other way to map 0-9 to P-Y.

  ! " # $ % & ' ( ) * + , - . / 
0 1 2 3 4 5 6 7 8 9 : ; < = > ? 
@ A B C D E F G H I J K L M N O 
P Q R S T U V W X Y Z [ \ ] ^ _ 
` a b c d e f g h i j k l m n o 
p q r s t u v w x y z { | } ~ ⌂

Tuesday, January 03, 2017

[uaskrdtz] Mapping letters to numbers in ASCII

A way to map letters to numerals, based on the ASCII table printed 32-wide, is 0 .. 9 = P .. Y. This is a bit surprising; one might have expected the digits to line up with the beginning of the alphabet.  The digit block does line up with a multiple of 16.

It suggests adding Z for base 11.

[kghqxjsk] Malcolm X as Old Testament

The Old Testament is about customs of tribes, tribes defining their identity (often through military victories and losses).

Malcolm X spoke of black identity, and using that identity as a foundation for political strength. 

The New Testament is about breaking down the tribal barriers and uniting around broader concepts like compassion.

Martin Luther King, Jr., a Christian minister by training, spoke of people of different races united as brothers and sisters.

The debate between them is very, very old.

Monday, January 02, 2017

[xvafqsgw] Default text color and background

Try setting the default text color and background in a web browser (e.g., Firefox) to light on dark to see how many web pages become unreadable.  Many webpages specify either a dark text color or (xor) a light background color but not both, causing either dark-on-dark or light-on-light when one changes the defaults to light on dark.  Light on dark is useful in dark ambient environments.

The ability for users to set their default colors and fonts seems to be disappearing from browsers, though still present in desktop Firefox.  User stylesheets are also useful.

For reference, to set default colors using attribitues body tag (works up to HTML 4.01, not supported in HTML5):
<body text="#000000" bgcolor="#ffffff" link="#0000ee" vlink="#551a8b" alink="#ee0000">
Or with CSS in the HEAD section:
<style type="text/css"> body { background-color: white ; color: black } a:link { color: #0000ee } a:visited { color: #551a8b } a:active { color:#ee0000 }</style>

Source code in Firefox specifying default colors.

[nhstyeva] Loopiness of a season

Given a collection of games between players (or teams), find as many nontransitive loops as possible, e.g., A beats B, B beats C, C beats A.

Such loopiness may signal a well-designed sport: there are many ways to win, many ways to lose.

[xevirvht] gpg setpref string

gpg --edit-key

setpref S9 S10 S13 S8 S12 S7 S4 S11 S3 S1 S2 H11 H9 H10 H8 H3 H2 H1 Z0 Z3 Z2 Z1 mdc no-ks-modify

This translates to (showpref)

Digest: SHA224, SHA384, SHA512, SHA256, RIPEMD160, SHA1, MD5
Compression: Uncompressed, BZIP2, ZLIB, ZIP
Features: MDC, Keyserver no-modify

Principle on ciphers and digests: Be liberal in what you accept.  This is much more ciphers and digests than the default preferences.  It is hard to imagine, but if a sender wants to send you something but can only use some weird but still-believed-to-be-secure ciphers, there's no reason to stop them.  I suppose it does open you up to exploits in rarely used code paths as you decrypt.

Prefer ciphers with larger keys over smaller keys.  Prefer ciphers with larger block sizes over smaller.  Prefer AES family over other less scrutinized ciphers.  Prefer Bruce Schneier ciphers because maybe his popularity has caused his ciphers to be more scrutinized.

Digests (hash functions): prefer digests which do not dump their entire state.  Prefer shorter digests over long, because that affects message size.  (I suppose cipher key size also affects message size.)  Accept MD5 because collision attack is not applicable.

Compression: prefer no compression because compression can leak information about the plaintext.  But if you are going to use compression, then use the best one.

The list of features available appears not to be documented anywhere.  Reading the source code, 1.4.21, those are the only two features available.

Beware that in 1.4 and 2.0, setting the preferences of a secret key, then exporting then importing the secret key will reset the preferences to default.

Finally, consider increasing the number of password hashing iterations protecting your private key.

[wmlnpsuf] Most efficient universal CA computer

Given a specification of a universal cellular automata, for example Conway's Game of Life, what is the most efficient implementation of a universal (Turing-complete) computer in it?

Considerable subjectivity: different measures of efficiency (e.g., compactness or number of generations per clock tick), and different computations to run on implemented universal computer.

Minimize the Life Unit Cell needed to simulate itself.

Sunday, January 01, 2017

[yactpuij] Observations of the leap second

The following script documents the system clock going backward at the leap second.

for (( i=0 ; ; i++ ))
do echo -n $i" "
date --iso=ns

Feed into gzip or bzip2 or xz then kill the script process by PID (not ^C, because that will kill the compression program).

Ubuntu 14.04

13293621 2016-12-31T18:59:59,996480552-0500
13293622 2016-12-31T18:59:59,998502752-0500
13293623 2016-12-31T19:00:00,000424730-0500
13293624 2016-12-31T19:00:00,002255494-0500
13293625 2016-12-31T19:00:00,003949090-0500
13293626 2016-12-31T19:00:00,005448105-0500
13293627 2016-12-31T18:59:59,007054958-0500
13293628 2016-12-31T18:59:59,008465206-0500

Ubuntu 16.04

45948121 2016-12-31T18:59:59,999325546-05:00
45948122 2016-12-31T18:59:59,999808163-05:00
45948123 2016-12-31T19:00:00,000337888-05:00
45948124 2016-12-31T19:00:00,000877926-05:00
45948125 2016-12-31T19:00:00,001407343-05:00
45948126 2016-12-31T19:00:00,001934319-05:00
45948127 2016-12-31T19:00:00,002418765-05:00
45948128 2016-12-31T19:00:00,002899595-05:00
45948129 2016-12-31T19:00:00,003372363-05:00
45948130 2016-12-31T18:59:59,004051384-05:00
45948131 2016-12-31T18:59:59,004808767-05:00

The following script is described here.  We can observe the repetition of 23:59:33 as the system clock goes backward (as above), then later 23:59:60.

for (( i = 0 ; ; i++)) ; do echo -n $i" " ;TZ=right/UTC date --iso=ns ; sleep 0.33 ; done

56853 2016-12-31T23:59:31,198116288+0000
56854 2016-12-31T23:59:31,530940907+0000
56855 2016-12-31T23:59:31,863877362+0000
56856 2016-12-31T23:59:32,196930593+0000
56857 2016-12-31T23:59:32,529740731+0000
56858 2016-12-31T23:59:32,863085326+0000
56859 2016-12-31T23:59:33,196001280+0000
56860 2016-12-31T23:59:33,528957882+0000
56861 2016-12-31T23:59:33,862031907+0000
56862 2016-12-31T23:59:33,194771050+0000
56863 2016-12-31T23:59:33,527665662+0000
56864 2016-12-31T23:59:33,861096024+0000
56865 2016-12-31T23:59:34,194124683+0000
56866 2016-12-31T23:59:34,527900279+0000
56867 2016-12-31T23:59:34,861187587+0000
56940 2016-12-31T23:59:59,175893786+0000
56941 2016-12-31T23:59:59,508957877+0000
56942 2016-12-31T23:59:59,841721314+0000
56943 2016-12-31T23:59:60,174499990+0000
56944 2016-12-31T23:59:60,507358020+0000
56945 2016-12-31T23:59:60,840145798+0000
56946 2017-01-01T00:00:00,173087257+0000
56947 2017-01-01T00:00:00,506015576+0000
56948 2017-01-01T00:00:00,838836886+0000

Future project: observe what happens to the RTC (hwclock).

Saturday, December 31, 2016

[aamtoufg] Observing the leap second (at the wrong time)

First, find out what time the leap second will occur in your local timezone:

$ date '--date=TZ="right/UTC" 2016-12-31 23:59:60'
Sat Dec 31 19:00:26 EST 2016

Then, as that time approaches:

$ TZ=right/EST date

You can substitute right/UTC for right/EST if you wish to see the leap second in UTC.  You can also substitute things like right/America/New_York.

Simulation of what should happen, by artificially setting the date:

$ TZ=right/EST date '--date=TZ="posix/EST" 2016-12-31 19:00:25'
Sat Dec 31 18:59:59 EST 2016
$ TZ=right/EST date '--date=TZ="posix/EST" 2016-12-31 19:00:26'
Sat Dec 31 18:59:60 EST 2016
$ TZ=right/EST date '--date=TZ="posix/EST" 2016-12-31 19:00:27'
Sat Dec 31 19:00:00 EST 2016

Note well, this will mark the leap second some 26 seconds after it actually occurs.  Details of why in the previous post. Also more information about the "right" timezone database.

You may also wish to add --iso=ns (nanoseconds) to date, or wrap the whole thing in a loop:

while true ; do ... ; done

Or add a sleep 1.

Observing the leap second at the wrong time has the benefit that the computer has settled down to a steady state by then, so you won't see additional weird things happening as the leap second actually occurs, as the computer resets its system clock.  One can try something hacky like the following to cause __:59:60 to display at the actual leap second,

$ TZ=right/EST date --date=@$(( $(date +%s) + 27 ))

but the computer behaves weirdly at the actual leap second. The above command will be 1 second too fast before the leap second, hold 18:59:60 for 2 seconds (the latter of which is the actual leap second), then be correct after the leap second.  Changing to +26 will be correct before the leap second, hold 59:59 for 2 seconds (including during the leap second), display 59:60 (1 second after the leap second), then continue to be 1 second slow afterwards.  Here is a simulation of +27:

$ TZ=right/EST date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 18:59:58' +%s) + 27 ))
Sat Dec 31 18:59:59 EST 2016
$ TZ=right/EST date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 18:59:59' +%s) + 27 ))
Sat Dec 31 18:59:60 EST 2016
$ TZ=right/EST date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 19:00:00' +%s) + 27 ))
Sat Dec 31 19:00:00 EST 2016

Another silly hack: if one is going to observe the leap second at the wrong time, then one might as well observe it at local midnight.

$ TZ=right/UTC date --date=@$(( $(date '--date=TZ="posix/EST" 2016-12-31 23:59:59' +%s) + 26 - 18000)) '+%r %Y'
11:59:59 PM 2016
$ TZ=right/UTC date --date=@$(( $(date '--date=TZ="posix/EST" 2017-1-1 0:00:00' +%s) + 26 - 18000)) +'%r %Y'
11:59:60 PM 2016
$ TZ=right/UTC date --date=@$(( $(date '--date=TZ="posix/EST" 2017-1-1 0:00:01' +%s) + 26 - 18000)) '+%r %Y'
12:00:00 AM 2017

The following script will try to tick the seconds at the correct time with subsecond precision:

while true ; do while [[ $(date +%N) > 090000000 ]] ; do : ; done ; TZ=right/UTC date --date=@$(( $(date +%s) + 26 - 18000)) '+%r %Y' ; sleep 0.9 ; done

Update: Some actual observations.

Wednesday, December 28, 2016

[bhqpyemy] These values are not pi

? log(640320^3+744)/sqrt(163)
? Pi

? log((640320^3+744)^2-393768)/2/sqrt(163)
? Pi


[vuptqpwg] Demonstration of RSA in Pari/GP

We demonstrate 16384-bit RSA below, slightly larger than the size (15360) recommended by NIST for the security level equivalent of 256-bit AES (symmetric) encryption.  Encryption (equivalently signature verification) was pretty fast (averaging 0.79 milliseconds (790 microseconds) over repeated trials).  Decryption, with its much larger exponent, is much slower, though still tolerable (0.76 seconds).

We generate p and q with precprime, obviously not random, because it is a compact and easy way to get a large prime number.  It also provides example timings of how long it might take to find a 8192-bit prime number.  The purpose \g5 is to catch if or when Pari/GP is trying to do a large futile factorization.  (Aside: it will try to do such a factorization when f is computed as f=eulerphi(n).  But this can be made to complete in 537 milliseconds by preceding it with addprimes(p).)  The most significant magic is the inversion of e modulo f, where f is not a prime.

GP/PARI CALCULATOR Version 2.7.5 (released)
amd64 running linux (x86-64/GMP-6.0.0 kernel) 64-bit version

? #
timer = 1 (on)
? s=2^8192
? p=precprime(s)
time = 34,720 ms.
? q=precprime(p-1)
time = 42,080 ms.
? p-s
? q-s
? n=p*q
? f=(p-1)*(q-1)
? \g5
debug = 5
? e=65537
? gcd(e,f)
? d=lift(Mod(e,f)^(-1))
? lift(Mod(e,f)*Mod(d,f))
? c=Mod(10^40,n)^e
time = 4 ms.
? lift(c^d)
time = 829 ms.
? x=0;for(i=1,10,x=x+Mod(random(n),n)^d)
time = 7,569 ms.
? x=0;for(i=1,10000,x=x+Mod(random(n),n)^e)
time = 7,901 ms.
? \q
$ cat /proc/cpuinfo
model name : Intel(R) Core(TM) i5-4690S CPU @ 3.20GHz

Saturday, December 24, 2016

[nxhebfuc] 34 characters for English

A ... Z
thorn eng ampersand
( ) #

Parentheses -- a matched pair of delimiters -- allow hierarchically structured text.  Most obviously, sentences, paragraphs.

The number sign # functions like an escape character.  #a ... j map to digits (probably like #cegab).  #k and beyond might be common punctuation and other things for escaping, e.g., formatting, capitalization.  #( ... ) is intriguing.

The parentheses suggest that text encoded using these characters should actually be interpreted as Lisp program that emitting Unicode or more structured text.  Lisp makes common use of dash in identifiers to separate words (note CamelCase is not available in our encoding because no capitalization), but we also don't have dash.  Maybe identifiers are permitted to have spaces and every atom is surrounded by parentheses.  Or weirdly use apostrophe as a separator.  Or distinguish between one and two spaces.  Or identifiers with spaces are surrounded by a special form.  Or  add a dash or underscore, increasing to 35.

34 (or 35) is a bit larger than nice 32, though changing base is not a big deal.  Fitting within 36=6*6 might be useful.

[hknbgvds] Append B

Take a word or message (without spaces) and interpret it as value in base 26, encoded little endian: a=0, b=1,... z=25.  Messages ending in an arbitrary number of a's cannot be distinguished from each other, analogous to invisible leading zeroes: 7 and 007 are the same big-endian decimal value but have different meanings.

Standard trick to solve this problem (e.g., seen for binary messages for MD5 and SHA-1): append a "b" to the end of the message (most significant digit), then convert the little-endian message to a value.  When decoding a value, strip the trailing b.

Other simple ideas: permit spaces in the message and use space=0, a=1,... z=26.  Trailing spaces get lost, which might be fine.  If big-endian, then leading spaces get lost.

Having converted a message to a value, proceed with, e.g., encryption.  Computers can compute radix conversion very quickly.

Converting a value to an output encoding in some base is easy.  If leading zeroes are again relevant, convert first to binary then to the target base.

Inspired by the awkwardness of needing base 32 for a simple cipher .  This encoding may grow the message by a letter or two, so not quite fitting in the original template.  (Of course, one would never keep the original message template for real encryption.  Use some other template.)

Friday, December 23, 2016

[atlnktkv] Four movement keys

Movement keys needed on touchscreens: left right home (beginning of line) end (of line).  Up and down are less needed; fingers can point with reasonable precision vertically because characters are tall.  Inspired by the Google Android keyboard (Gboard) which provides left/right navigation by sliding on the spacebar, but could use home and end.  A very long single line text field (URL) needs lots of scrolling to reach the beginning.


[knkpgwyf] Precognition in a game

One can simulate precognition, a character with the ability to see the future, in a game by allowing the player to roll back time (undo).  Probably helpful if opponents are deterministic.  Then play the time stream as performance.

Inspired by Jedi.

[ehitzrcs] Prime generating sequence

Is the computationally most efficient way to find a prime number of a given (large) size to search either for a Mersenne prime (Lucas-Lehmer) or test random numbers with some other well-known general prime number test (probably slower than LL by only a constant factor)?  (Consider trying to win the EFF Cooperative Computing Award.)  Can this be proven?

A counterexample might be an easy-to-compute sequence that is significantly denser in primes than simply the integers filtered by sieving.  Prove no such sequences exist.

[xnrnnfbo] Double predation

The cat has been stalking the mouse.  It pounces, but in the midpoint of its pounce, the cat gets picked off in midair by a large predatory bird or other larger predator which had been stalking the cat.

[uaouyxpg] Darth Vader as Terminator

Depict Darth Vader as an unstoppable unassailable archvillain in a story taking place slightly before Star Wars Episode 4.  The rebels are justifiably scared shitless of him.

Inspired by criticism of Rogue One.

Monday, December 19, 2016

[xrzqvpap] Shaped text

Any text can have its spacing, punctuation, and capitalization altered to match that of another template text.  Not sure what this might be useful for, perhaps a red herring to throw off cryptanalysis.

Aaaaaaaa aaaaa aaaa aa aaa aaaaaaaaaa aa aaaaaaaaaaaaa aa aaaaaaaa, aa aaaaaaaaaaa aaa aaaa aaaaaaaa aaaaaaa; aa aaaaaaaaa aaa aaaaaaa aa aaaaaa, aa aa aaa aaaaa; aa aaa aaaaa aa aaa aaaaaa aaaaaaaaa aa aaaaaaaa, aaa aa aaaaaaaa aaa Aaaaaaaaaa aaa a aaaaaaa aa aaaaaaaaaa.

Below are 676 digits of the square root of 26, expressed in base 26.

Fcoyjobw xilky rtoh vk auh zedskehhup gj sijceekmbkyct pz rnryxgod, fn vmcwaflvtwm anx cwqa zdssfhnp biwmzqg; yz qrbaskigw gla ovaewrz ry paovvi, se yu yvz jcjua; ns kin naqgk rj zlo fkmawm snrnwchns mi peoywtwx, zpq eu ifpaaaag bop Pynztcaubp ivr u htdmmdf au tottjmkzaq.  Oyilmswk dtxzt ouiy pc ill plyhcjiebb ba udaeosjqkyrls fs pcttqana, tb vwynrdefmcu rdb ebyj tcvxvwhf wgazyya; ei bmylkbeso zcq xmbghrl pn yyhxkx, tm az edh rbwfn; wc tru zpdtx oi xuk omglbo puhfvtxdx fq cgyihcgo, pcn so vzhrshsk esk Oiejnnqqnf ktx x kdybkrh ct cfhmxagkfk.  Fjublacd zpdhh luam dy zvw bklkxxegju qj iuofdjhgezynz eu dkrqyeob, wg smpaotpxvmn vth mprl chxgblwh bcpnfdi; oy koqtnhiyg yas zoioawb xx uimdfq, ly fb lza vfntd; eo khi wbkef hc krj sywuyh ryudavaci uj zvtvsvqe, shl nc oaeofxuu rnr Xycfcathfy eal x ygwlkqx ns vrzchdfmgc.  Scthvbpv uy

The template text is the First Amendment, used previously, cycled as many times as necessary.

Source code in Haskell.  We create a "template" describing the pattern of capitalization and punctuation, then zip it with text, except we do not use zip, but instead unfold (unfoldr), because punctuation elements in the template do not consume any text, so zip does not quite work.

Friday, December 16, 2016

[ripsdmzo] Equality of algebraic numbers

Given two algebraic numbers, determine if they are equal; equivalently, given an algebraic number, determine if it is equal to zero.

Intuitively, this problem seems difficult, perhaps intractable.  However, if the algebraic number is specified as a polynomial with integer coefficients, it does not seem so hard: is the constant term zero?  Perhaps the difficulty is in specifying which root of the polynomial.

[yyqaqeer] Instant factoring

What is the largest size general numbers which can be factored "instantly" according to human perception?  Provide it as a function in a calculator app (but it is a function that returns multiple values).  (Actually, returning just the least prime factor would be useful.)

Which algorithm should be used?  The crossover point where the number field sieve becomes more efficient than quadratic sieve is probably way beyond the timescale of "instant" so NFS will not be needed.  Experiments with Pari/GP find that quadratic sieve does produce useful results within 100 milliseconds.

We want a highly optimized parallel implementation to take advantage of multicore.  (This is the only failing of Pari/GP.)

Trying other algorithms leads to messy questions.  Other algorithms, e.g., elliptic curve method, tried before quadratic sieve can decrease average running time but will increase worst case running time.

The only factorizations useful for most people are probably either less than around 10000 (or smooth so that all factors are less than 10000) or greater than 2^1024 (the latter effectively impossible), so providing quick factorizations of medium sized numbers is probably overkill.

[ujpfhpfl] Comparing Brotli text compression with gzip xz bzip2

Original file is a highly repetitive log file of software compiling.

116530086 h10.log
 15689146 h10.log.bro1
 13353595 h10.log.gz
 13150100 h10.log.gz9
  7636694 h10.log.bz2
  7277693 h10.log.bro9
  6632700 h10.log.xz
  6327414 h10.log.bro10
  5905125 h10.log.bro11
  5905125 h10.log.bro
  5706828 h10.log.bro-w24

gz9 is gzip -9.  broN is bro with -q N.  Brotli defaults to --quality 11 (the maximum), which is a fun reference to Spinal Tap, but is highly unintuitive compared to every other compression program which only goes up to 9.  And brotli has no manpage or usage documentation (true to Google style) to find this out.  bro-w24 is bro -w 24.

[rjmvxijx] Bending the fundamental forces

Significantly modify "Avatar: The Last Airbender" so that the 4 elements are not earth, air, water and fire, but the 4 fundamental forces of nature, gravity, strong nuclear force, weak nuclear force, and electromagnetism.  Benders who can manipulate those forces can do amazing things.  Certain benders can manipulate more than one, unifying some forces in the order seen in reality, and the rarest bender, the avatar, has unified all 4, analogous to the Theory Of Everything.

[kplnpdhr] Find positions which engines differ

Given two chess engines, find positions about which they significantly disagree on evaluation.  This might be a good task for machine learning.

Then, of course, improve the engine which is making the bad evaluation.

[elhqodnx] The Bible advocating modern genocide

Extract quotes of the Bible advocating or celebrating genocide and replace the names of the targets/victims with whomever extremists want to genocide this week.  (This of course is already being done.)  Deuteronomy 7, Deuteronomy 20, Joshua 11, 1 Samuel 15 is the most explicit.

Particularly poignant might be to modify it in the original language: Masoretic Text.

[rtmtblnr] Star Politics

Take just the politics aspect of The Phantom Menace dial it up to 11, making a whole movie about political maneuverings in a galactic government.  It initially might seem to be the worst idea ever, but perhaps not so bad: space politics as an allegory for human politics on planet earth.

Every deal, every decision, affects trillions of beings or more.

[lybrkesb] Testing all Chess960 initial positions

When inventing Fischer Random Chess, did Bobby Fischer carefully analyze all 960 initial positions to make sure none were hugely unbalanced (e.g., white has a forced line that can gain winning advantage, or black can easily force a draw)?  If so, that is impressive Edison-level perspiration that very few people could have done in the days before chess engines.

There were also the rejected chess variants that didn't end up becoming Chess960.

[udcchqhe] Argon2 4TB limit

The Argon2 password hashing algorithm has a hardcoded 4 terabyte (tebibyte) maximum limit of memory it can be specified to use.  This seems like a terrible idea -- the limit (if any) should be much higher.  Can Argon2 be easily extended to use more memory?

There are computers right now that have over 4 TB of RAM (granted, they are supercomputers) and that much RAM or more will likely become more accessible in the near future.  (The addressable limit -- currently 8 TB for amd64 -- will also likely increase.)  Furthermore, even if they don't become commonplace, an organization for whom security is very important might get a single expensive computer dedicated to password hashing, making attacking a hashed password very expensive for adversaries.

Repeating the Bill Gates mistake: N units [of memory] should be enough for everyone.

[cdalfncq] Encrypting with a visual puzzle

In addition to encrypting sensitive data with a password, also consider additionally encrypting it in a way that requires solving a CAPTCHA-like puzzle.  Details remain about how to implement it and what the UI should look like.

Threat model: the legitimate user already knows what documents he or she wants to access, so can go directly to it, solving a few CAPTCHAs.  The illegitimate user -- e.g., surveillance or forensics -- wants to scan the entire computer or system or stream for something but will have to solve a CAPTCHA for each item -- each file -- scanned.


[nfypbdyk] Multicore compression

Two ways to parallelize data compression:  Compress multiple different blocks in parallel, or have multiple different cores working on the same block, perhaps exploring different ways to compress the block.  The latter is not done too much, but could be and should be: there are some extremely slow but powerful compression algorithms out there that do significantly better than what is widely available.  Maybe parallelization will exhaust memory before exhausting number of processor cores.

[dbcpqerb] Cantor hypercomputer hierarchy

A hypercomputation does an infinite amount of computation in finite time; perhaps each clock cycle is half the length of the previous one, in the style of Zeno's paradox.  (Such a computer cannot realistically be built.)  This can, say, test a property over all integers or all rational numbers.  Supertask.

More powerful would be to test over all real numbers.  More powerful would be to test over all functions over real numbers.  And so on up the Cantor hierarchy of infinities: aleph or beth numbers.

Which computer can calculate the halting probability of a random Turing machine?  I think "all possible Turing machines" is a countable set, and of course the number of cycles a Turing machine runs is also countable.

When a powerful computer capable of testing over all reals or functions runs, what does its output look like?  Find me a noncomputable real number, we tell it.  OK, here is one, it responds, but what does this output look like?  Perhaps the text string "the halting probability of a random Turing machine".

Monday, December 12, 2016

[lkuzxate] Who to have more babies?

Suppose a country, for example, Japan, is struggling with negative population growth, and wants to provide incentives for people to have more children.  How should the incentives be structured?  In particular, should it be designed to result in many families having slightly more children, or a few families having many more children?

The latter might be more efficient through economies of scale but potentially causes problems with only a small number of parents defining the culture of the next generation.

[jsvxprhp] Pong circular paddle

In the classic computer game Pong, the angle the ball bounces off the paddle depends on where on the paddle the ball hits.  This could be nicely illustrated by making the paddle shaped like a semicircle.

Several difficulties: the bounce point is no longer strictly on the back wall -- the plane of a flat paddle; it may be separated from the back wall by the radius of the paddle.  Should the momentum of the paddle become transferred to the ball?  If so, how much?