[ykierhyf] tilings of triangles and squares

tile the plane with squares and equilateral triangles all of the same side length.  this could be fun with physical tiles.

well investigated are the regular, semiregular, and uniform tilings, but random tilings also seem possible.

possible vertex configurations are (4 squares), (6 triangles), and (2 squares and 3 triangles).  2+3 has 2 possibilities: whether or not the squares are adjacent.

how careful do you need to be to avoid creating a gap into which nothing fits?

(as of early 2026, AI image generators failed to draw this random tiling.)

how difficult are such tilings to 4-color?  I think the following works: assign squares 2 colors.  2-color in a checkerboard pattern every connected component of just squares.  similarly, triangles with the other 2 colors.

this pair of tiles feels vaguely similar to Penrose tiles.  squares and triangles can tile periodically but they don't have to.

the edges form a penny graph.  these graphs feel aesthetically dense like the square and triangular grids.  the graph formed by the edges of the regular hexagon tiling does not feel aesthetically dense.

[kacgvdua] maximal Steiner tree

given a connected graph and a number N, select N vertices in the graph so that the size of the Steiner tree (Steiner tree problem on graphs) spanning the selected vertices is maximized.  (by definition, a Steiner tree minimizes its size, so this is a maximum-minimum problem.)  the size of a Steiner tree is sum of the weights of all its edges.  if unweighted edges, let every edge have unit weight.

if N=2, then the size of the maximum Steiner tree is graph diameter.  for larger N, this generalizes graph diameter: find the N points farthest away from each other.

for an adventure game exploring a graph, these are where the treasures are hidden.

what is the computational complexity of this problem?  solving the Steiner tree problem on graphs just once is NP-complete; now we are solving it binomial(number of graph vertices, N) times.

[ksnmkfky] pixel glyphs

given a region partitioned into a small number of pixels not necessarily square (future post cmpvevta), enumerate glyphs.  two possible pixel colors, denoted background and foreground.  simplest enumeration: with N pixels, 2^N glyphs.

more complicated: avoid glyphs the same after translation.  avoid rotations, so text written sideways or upside down does not change meaning.  avoid reflections, making life easier for dyslexics.

only one connected component of foreground pixels.  strictly more (or less) than half the pixels are foreground.  or, avoid glyphs the same after inversion, swapping foreground and background.  (this might be useful for designing symbols for fairy chess, where we want both a black and white version of symbols.)

avoid not only "same" but also similar, within a given Hamming distance.  maximize the number of distinct symbols.

[argeufrf] automatic field separator

unless this is to be first field (e.g., word) in the line (record), print the field separator (e.g., space for words in a line, comma for CSV, tab for TSV).  then, print the given field data.  the output subsystem automatically keeps track of whether we are at first field in a record.

optionally, automatic escaping or quoting if the field data contains a field or record separator.

similarly, automatic record terminator (e.g., newline) on orderly file close.

in general: field prefix, field terminator, field separator, record prefix, record terminator, record separator.  not all of these will be used.

[lzlpplvi] shortest path on a Euclidean manifold with wormholes

in Euclidean space, the shortest path between two points is a line segment.  then, modify the space:

designate two special points for which travel between them is free, costs no distance, i.e., a wormhole connects the points.  then, the shortest path between two points might no longer be the line between them; it might be to travel to and from the wormhole mouths.

(which pairs of points are affected?  this is a problem in 2*D dimensional space.)

instead of just two special points, add a line of special points with free travel between any two points on the line.  shortest paths will often involve traveling orthogonally to the line, traveling along the line for free, then departing orthogonally from the line to the destination.  maybe this is a river in which transportation cost is negligible.  or, minimize walking where there are moving sidewalks.

the wormhole mouths and river line are examples of sets of points.  a zone of free travel can be generalized to any set of points.  one could have multiple zones: free travel within each zone, but, unless zones are adjacent, you have to exit a zone and travel through the overworld to connect to other zones.

how difficult is finding the shortest path?

once we have a notion of shortest path (geodesic), we can define minimum spanning tree, traveling salesman, Euclidean Steiner tree, Voronoi diagram, Delauney triangulation.

[lyncpmou] expected number of barriers passed

let barrier(n,h) be the probability of passing barrier number n, starting from n=1.  h is a parameter that will be used later.

to pass exactly n barriers, one needs to consecutively pass barriers 1 through n, then fail barrier n+1:

exactly(n,h)= prod(i=1,n, barrier(i,h)) * (1-barrier(n+1,h))

(Pari/GP syntax)

the expected number of barriers crossed before the first failure is an infinite sum.  here is the partial sum:

partialexpected(n,h)= sum(i=1,n, i*exactly(i,h))

first, let us investigate the barrier probability being a constant, not dependent on n:

barrier(n,h)= h

the expected number E of barriers crossed for constant barrier probability h:

h=1/6 E=1/5
h=1/5 E=1/4
h=1/4 E=1/3
h=1/3 E=1/2
h=2/5 E=2/3
h=1/2 E=1
h=3/5 E=3/2
h=2/3 E=2
h=3/4 E=3
h=4/5 E=4
h=5/6 E=5

the above exact values are conjectures from the partial sum, e.g.:

partialexpected(999,5.0/6)
4.9999999999999999999999999999999999940
cpu time = 107 ms, real time = 107 ms.

a closed-form formula for a given constant barrier probability is probably not difficult to derive, probably something like geometric series.

if the barrier probability is 1/n, the expected number of barriers crossed is e-1:

barrier(n,h)= 1.0/n
partialexpected(99)
1.7182818284590452353602874713526624977
partialexpected(98)
1.7182818284590452353602874713526624977

the second calculation of only 98 terms verifies convergence of the partial sum.  a barrier probability decreasing as a function of n is nice for making the partial sum converge quickly.

(in Pari/GP, if a function argument is omitted -- in this case h -- it is assigned a default value of 0.)

if the barrier probability is 1/(2*n), equivalently 0.5/n, then the expected value is exp(0.5)-1 (via the RIES Inverse Symbolic Calculator). (the original Inverse Symbolic Calculator has gone offline.)

barrier(n,h)= h/n
partialexpected(99,0.5)
0.64872127070012814684865078781416357161

we conjecture that the expected value for this form of barrier probability is exp(h)-1.  therefore, if h = log(2) ~= 0.693, the expected value is 1 :

partialexpected(99,log(2))
0.99999999999999999999999999999999999996

let the barrier probability decay exponentially:

barrier(n,h)= h^n

if the barrier probability is 1/2^n , then the expected value has the following value, unknown if it has a closed form:

partialexpected(99,0.5)
0.64163256065515386629384277022542943422

if h = 0.7 , the expected value is greater than 1 :

partialexpected(99,0.7)
1.1942513927487148419874371583834978589

we use Pari/GP's nifty solve function to find the value of h such that the expected value is exactly 1 .  does this value of h have a closed form expression?

h = solve(x=0.5,0.7, partialexpected(99,x)-1)
0.64522270323602097913425166394402633225
partialexpected(99,h)
0.99999999999999999999999999999999999996

recall that if the barrier probability is 1/n, the expected value is e-1 :

barrier(n,h)= 1.0/(n+h)
partialexpected(99,0)
1.7182818284590452353602874713526624977

the first barrier is passed with probability 1, not a barrier at all, a free +1 to the expected value.  if we shift all barriers by one, then the expected value is unsurprisingly e-2 :

partialexpected(99,1)
0.71828182845904523536028747135266249771

this is the amount of shift that makes the expected value 1 :

h= solve(x=0,1, partialexpected(99,x)-1)
0.53571808926964201274443895890553620494

let the barrier probability obey a power law.  we shift by 1 to skip the free first barrier:

barrier(n,h)= (n+1.0)^h

when the exponent is -1, the expected value is e-2 as noted before:

partialexpected(99,-1)
0.71828182845904523536028747135266249771

if the probability is 1/sqrt(n+1) , the expected value is greater than 1 :

partialexpected(99,-0.5)
1.4695063145210475624756367446601502576

this exponent makes the expected value 1 :

h= solve(x=-0.5,-1, partialexpected(99,x)-1)
-0.73888040289770820386751815624320497895

inspired by modeling family sizes.  have children until you can't, perhaps because of death caused by complications from childbirth.

if sampling a random tree where the number of children of each node has expected value 1, the population stays approximately constant generation to generation (I think).  such a tree models asexual reproduction, or a filtered view of sexual reproduction paying attention to only one gender.

[jnqlnxts] classification of extensive-form games by computational requirements

game length:

1. infinite-length games possible.  (if finite game state, then game must be loopy.)
2. games are guaranteed to be finite length but finite games of arbitrary length possible.  (e.g., players take turns naming smaller positive integers, Kirby-Paris hydra.)
3. maximum game length known at start.

this classification is practically fuzzy: maximum game length could be finite but so large as to effectively be infinite (future post hxfdvhup).  (e.g., loopy games with special rules prohibiting repetition.)  or, infinite or extremely long games are theoretically possible but require both players to be silly.

game state:

bounded or unbounded amount of information needed to describe game state.

common case of unbounded: loopy game has special rules regarding repeating a previous position (e.g., chess 3-fold repetition, go 囲碁 super-ko) so, as the game progresses, game state includes a growing list of positions already seen (in practice, a hash table).

this classification is practically fuzzy: theoretically bounded but so huge as to effectively be infinite.  chess and go 囲碁 have finite numbers of possible positions so keeping track of all of them classifying each as already seen or not requires only a finite bounded (but huge) amount of information.

the above classifications matter for computer implementations of games: how many bits wide should the move counter be to avoid overflow?

other famous classifications: perfect vs. imperfect information (players hide information).  complete vs. incomplete information (randomness or chance).

[tgtdtucz] Fourier series for ellipse in polar coordinates

below is the formula for an ellipse in polar coordinates, with eccentricity e and one focus at the origin (multiply by scaling factor to embiggen):

r = 1 / (1 - e*cos(t))

the formula has cosine in denominator.  we compute its Fourier transform to get a formula with the sines and cosines only in the numerators.  (only cos is needed.)

Mathematica:

FourierCosSeries[1/(1-e*Cos[t]), t, 7, Assumptions-> e < 1 && 0 <= e] //Timing

{245.35853, 1/Sqrt[1 - e^2] + (2*(-1 + 1/Sqrt[1 - e^2])*Cos[t])/e - (2*(-2 + e^2 + 2*Sqrt[1 - e^2])*Cos[2*t])/(e^2*Sqrt[1 - e^2]) + (2*(-4 + 4/Sqrt[1 - e^2] + e^2*(1 - 3/Sqrt[1 - e^2]))*Cos[3*t])/e^3 + (2*(8 + e^4 - 8*Sqrt[1 - e^2] + 4*e^2*(-2 + Sqrt[1 - e^2]))*Cos[4*t])/(e^4*Sqrt[1 - e^2]) - (2*(16 - 16/Sqrt[1 - e^2] + e^4*(1 - 5/Sqrt[1 - e^2]) + e^2*(-12 + 20/Sqrt[1 - e^2]))*Cos[5*t])/e^5 - (2*(e^6 + e^2*(48 - 32*Sqrt[1 - e^2]) + 6*e^4*(-3 + Sqrt[1 - e^2]) + 32*(-1 + Sqrt[1 - e^2]))*Cos[6*t])/(e^6*Sqrt[1 - e^2]) + (2*(e^6*(-7 + Sqrt[1 - e^2]) - 64*(-1 + Sqrt[1 - e^2]) - 8*e^4*(-7 + 3*Sqrt[1 - e^2]) + 16*e^2*(-7 + 5*Sqrt[1 - e^2]))*Cos[7*t])/(e^7*Sqrt[1 - e^2])}

what is a general formula for the coefficients (to get an infinite series)?  this has almost certainly already been solved, but I could not find such a formula published anywhere.  it seems like the kind of thing Joseph Fourier might have done himself.

investigate Fourier transforms of generalizations of the original formula with cosine in the denominator, for example, r(theta) = 1/(sum(n, A[n] * cos(n*theta + B[n]))).  what is the Fourier transform of the reciprocal of a Fourier transform?  previously, polar plots of regular (not reciprocal) Fourier series.  under what conditions is the shape convex?

[gjjimaii] estimating pi with primes

we compute an approximation of Riemann zeta(2) = pi^2/6 using the Euler product formula over primes, then solve for pi:

? for(n=0, 10, z=1; forprime(p=1, 10^n, z*=(1-(1.0/p^2))); print("10^"n" ",sqrt(6/z)))

pi estimated from the product of all primes less than 10^n:

10^0 2.4494897427831780981972840747058913920
10^1 3.0935921676911454192536940842087145469
10^2 3.1387371950717209555231899287777680519
10^3 3.1413931847879282123372947308786365411
10^4 3.1415772351603451399115522305263190950
10^5 3.1415913934202453316750296375573376397
10^6 3.1415925471279879791648160810012226847
10^7 3.1415926443848380990491814377585237930
10^8 3.1415926527790129584805149679019884804
10^9 3.1415926535173431626391708456483210697
10^10 3.1415926535832448165410657025850891080

cpu time = 7min, 50,161 ms, real time = 7min, 50,326 ms.

each power of 10 yields slightly more than one more correct digit.  asymptotically, probably just one digit, so this is not an efficient method of calculating pi, though it is nice to have gotten the digits above without too much effort.

previously, estimating e with primes.

[ynwwppvz] estimating e by counting primes

let n = 2^22 = 4194304.  there are p = primepi(n) = 295947 primes less than n.

using the prime number theorem n/log(n) ~= primepi(n), then e ~= n^(p/n) ~= 2.93 .

using n/(log(n) - 1) ~= primepi(n), then e ~= n^(p/(n+p)) ~= 2.732 .

(the same n was used previously computing e with primorial.  using the values of primes as we did then yielded slightly more precision (2.717) than using just their count as we do now.)

the typical way of computing fractional powers is with log and exp, but if you have such functions, then e = exp(1).

we chose n to be a power of 2 to permit easily computing the fractional power ^(p/n) in the first approximation without needing log and exp: the 1/n power in the can be computed by repeated square roots.  n^(p/n) = (n^p)^(1/n).  compute n^p first by augmenting machine precision floating point with an exponent that can become much larger than provided by the machine type.  the only operations one needs are multiplication and square root.  example implementation in Haskell.  there are some bits (pun!) of symmetry between exponentiation by squaring for the numerator of p/n followed by repeated square root for the denominator.

for the second approximation n^(p/(n+p)), one could have attempted to choose a different n such that n+p is a power of two.  but 3916608 + primepi(3916608) = 2^22-1 and 3916609 + primepi(3916609) = 2^22+1 (because 3916609 is prime), so it would have required some fudging.

better is to approximate the fractional exponent p/(n+p) as round(2^64 * p/(n+p))/2^64 .  (64 bits should be enough for everyone.)  for n = 2^22, p = 295947, this works out to to 1215802539408625636 / 2^64.

or, use Newton's method to compute the (n+p)th root of x^p.

comparing with methods that don't involve primes, but inputs of a similar scale:

e ~= (1+1/n)^n : for n=2^22, e ~= 2.718281504 .

sum(n=0, 10, 1.0/n!) ~= 2.71828180 , choosing 10 because 10! is the largest factorial less than 2^22 .

[sguflopg] prime(x) = N*x

the 6455th prime number is 64553, a factor of about 10.

here are a few variations on estimating the crossover point using the prime number theorem.

if approximating the nth prime by n*log(n) :

nthprime(i) = 10*i
i*log(i) = 10*i
log(i) = 10
i = exp(10)
i ~= 22026.5

crossover predicted around the 22026th or 22027th prime, namely 249779 or 249797.

if approximating primepi(n)= n/log(n) :

primepi(n) = n/10
n/log(n) = n/10
log(n) = 10
n = exp(10)
n ~= 22026.5

crossover at 22026.5 (bracketed by primes 22013 and 22027 which have indices 2466 and 2467 respectively).

if approximating primepi(n)= n/(log(n)-1) :

primepi(n) = n/10
n/(log(n)-1) = n/10
solve(n=1000, 100000, n/(log(n)-1) - n/10)
n ~= 59874.1417

crossover predicted around 59874.1 which is bracketed by primes 59863 and 59879 which have indices 6048 and 6049 respectively.  this is the best approximation, albeit not closed form.

because exp grows exponentially (like it says on the tin), we will never know the exact crossover for larger factors, e.g., 100.

enumerate the crossover points for small integer factors.  there is much sophistication available for counting primes without explicitly generating them.

as of 2022, the record evaluation of the prime counting function is primepi(10^29) ~= primepi(exp(66.8)) ~= 10^29/65.8 . it will take a little more work to find the crossover point nthprime(x) = 65*x.

[vzqpqtrb] some slowly diverging and slowly converging integrals

evaluate these improper integrals from (some suitable lower bound avoiding undefined values) to infinity.

In[]:= Integrate[1/(x^(1)), x]

Out[]= Log[x]

In[]:= Integrate[1/(x^(1+1/n)), x]

Out[]= -(n/x^n^(-1))

the first integral diverges as x tends to infinity; the second converges.

NB: exponentiation is right associative, so the above expression is equal to -(n/x^(n^(-1))) = -n/(x^(1/n)) .

digression: set n=1 to show Riemann zeta(2) converges; Basel problem asks for its exact value.

In[]:= Integrate[1/(x*(Log[x])^(1)), x]

Out[]= Log[Log[x]]

In[]:= Integrate[1/(x*(Log[x])^(1+1/n)), x]

Out[]= -(n/Log[x]^n^(-1))

In[]:= Integrate[1/(x*Log[x]*(Log[Log[x]])^(1)), x]

Out[]= Log[Log[Log[x]]]

In[]:= Integrate[1/(x*Log[x]*(Log[Log[x]])^(1+1/n)), x]

Out[]= -(n/Log[Log[x]]^n^(-1))

it is nice that these all have simple form.

future post: infinite product of iterated log.

previously vaguely similar: twin primes and LogIntegral

[cgratocc] product of shifted iterated logarithms

each term has value 1 at n = 0:

f1(n) = (n+1) * log(n + e) * log log(n + e^e) * log log log(n + e^e^e) * ...

or, each term has value 1 at n = 1:

f2(n) = n * log(n * e) * log log(n * e^e) * log log log(n * e^e^e) * ...

does the product converge for n>0 or n>1 respectively?  integrate 1/f from n=0 or n=1 respectively to infinity.  does it diverge?

previously on iterated log.

[lrppbqqi] word primes

below are the 129 primes less than 27^2 = 729, written in big-endian base 27, using the following straightforward encoding of base-27 digits:

a=1 b=2 c=3 d=4 e=5 f=6 g=7 h=8 i=9 j=10 k=11 l=12 m=13 n=14 o=15 p=16 q=17 r=18 s=19 t=20 u=21 v=22 w=23 x=24 y=25 z=26

b c e g k m q s w ab ad aj an ap at az be bg bm bq bs by cb ch cp ct cv cz da de ds dw eb ed en ep ev fa fe fk fq fs gb gd gh gj gv hg hk hm hq hw hy ih in it iz ja jg jk jm jw kj kn kp kt lg lm lw ly mb mh mp mv na ne nk ns nw od on op oz pa pg pk pq py qb qd qh qt ra re rm rq rw sh sj ta tg tq tw ub ud uj ut uz ve vg vm vs vw vy wj wt wv wz xe xk xm xy yb yh yp yz zg zq zy

there are 9 1-digit primes and 120 2-digit primes.

the digits c f i l o r u x corresponding to multiples of 3 never occur as the last (units) digit, except for c by itself.

for 1- and 2-digit primes, we do not need a symbol to represent zero.  the first digit cannot be zero because that would be a useless leading zero.  if the second digit were zero, the number would be a multiple of 27, so not prime.

future work: consider a prime base so that all letters can occur in the units place.  deal with the special case "10" by ignoring it.  what two characters should we add to reach the 28 letters needed for base 29, and where in the alphabet should we add them?  or which 4 should we eliminate for base 23?  (probably wxyz.)

for the 2098 3-digit primes between 27^2 = 729 and 27^3 = 19683 below, we do need a symbol for zero as a middle character.  we choose dash (hyphen), mimicking English orthography.  (apostrophe was another good option.)

for 4-digit primes and larger (not explored), we could have multiple dashes in a row which are hard to distinguish in fonts that meld them into a single line, so some other symbol (e.g., apostrophe) for zero would be better.  or, do base 26 instead of base 27: there will be no words starting with a=0.  (or, make z the zeroth letter.  x is another good choice for zero, unlikely to begin a word.)

these primes could be the dictionary for a weird game of Scrabble.  blank is zero.  reorder the alphabet so that the frequency of Scrabble letter tiles correspond to the frequency of letters among 2-digit primes.

which English words are primes?  this should be easy.  assuming we stick with base 27, choose a different mapping of letters to digits so that multiples of 3 correspond to the letters least likely to end a word.  or begin a word if encoding little-endian.  find the mapping of letters to digits that maximizes the number of prime English words.

a-d a-j a-n a-v aaa aae aam aaq abd abn abz aca ack acm acq acs adb adp adt adv adz aem aeq aes aew afp aft aga agk ags agw ahb ahh ahv ahz aie aik ais aiy ajj ajn ajt ajv ake akg akm akw aky alh alj alp amg amk amm amq amw anb anj anp anv aoq aos apb apj apt apz aqe aqm aqy arb arh arn arp arv asg asq ath atj atn att atv aua aue aug auk auw auy avd awk awq aww axd axv aye ays ayw ayy azb azh azp azt azv b-a b-m b-w b-y bab bad bah ban baz bbk bbs bcd bcj bcn bct bda bde bdm bdq bed beh ben bep bet bez bfa bfg bfq bgj bgp bgt bgv bhs bhw bhy bih bit biv bje bjm bjs bjy bkd bkv bla ble blg bls bmb bmn bmv bnk bny bod boh boj bon bop boz bpk bpq bpw bqn bqp bre brg bsb bsh bsp bsv bsz bta bte btm bts bub bud bun bva bvk bvq bwb bwd bwh bwj bwt bxe bxg bxw bxy byd byh byj byt bza bzs c-p c-t c-z cag caw cay cbb cbj cbz cca cce ccm ccs ccy cdb cdn cdp cek ceq ces cey cfb cfh cfv cga cge cgg cgm cgq cgw chh chn cht cig cik ciq cjb cjj cjp cjt cks clj clt cma cme cmk cmm cms cnn cnz coa coq coy cpb cpn cqa cqk cqm cqq cqy crd crj crn crp crt crz csg csk csm css ctb ctd ctn ctv ctz cum cuw cvh cvj cvp cvt cvv cwk cwy cxb cxh cxp cxv cxz cyq cyy czh czn czt d-a d-k d-w daj dan dat daz dba dcb dcd dcn dcv dcz ddm ddq ddy dej dep dfa dfe dfk dgd dgn dgp dhe did dih dij div dja dje djq djw dkd dkh dkp dlk dlm dlq dls dmd dne dng dnm dns dny dob doh doj dov doz dpk dpm dpw dpy dqn dqp dre drk dsd dst dta dte dtg dtk dtm duh dup dva dvg dvq dvs dvw dwb dwd dwj dwt dwv dxg dxq dxs dyb dyp dyv dyz dze dzm dzs dzy e-n e-z eaa eae eas eay ebb ebj ebt eca ecg ecm edh edn edp edz eem eeq eew efn efp efz egm egq egs ehb ehp eht eia eis eiw ejb ejd ejh ejn ejp eka eke eky elt eme emg emk emq emw emy end enz eoa eog eow epb epn epp epv eqg eqw eqy erb erh erv erz esa ess etp etz eue eug euq eus evb evd evn evt evv ewe ewg ewq eww exd eyg eyq eys ezb ezj ezp ezz f-q f-w fah fat fav fbm fbs fbw fcb fch fcz fda fdk fdy fed feh fej fen ffk ffm ffy fgd fgt fha fhg fhm fid fit fiv fiz fje fjg fjm fjs fkb fkh fkt fle flw fly fmd fmh fmz fng fod foh foj fon fot fov fpg fpk fpy fra frk frq fsb fsp fsv fte ftq fts ftw fub fuj fup fuz fva fve fvs fvy fwd fwh fwn fwp fwz fxa fxq fyb fyj fza fze fzk fzw fzy g-d g-j g-p gaq gaw gbj gbn gbv gce gcm gcy gdp gdt gdv gdz gew gfh gfn gfp gge ggk ggq ghd ghn gia gie gjh gjn gjt gjz gkg gkm gkq gks gld glj gln glp glv gmq gmw gmy gnb gnt gnv gnz gok gom gos gow gpv gqa gqg gqk gqs grb gsg gsw gsy gtd gth gtj gtn gtp gtz gum gus guw gvd gvn gvt gwm gwq gws gwy gya gye gym gyw gzb gzh gzp gzv h-g h-k h-q h-s h-y hab hah haj hat hav hbk hbq hcj hcn hcz hdm hen het hfm hfq hgh hgp hgv hgz hhe hhs hhy hid hin hip hiz hjk hjs hkb hkd hkn hkv hlg hlq hmn hmp hmt hna hng hnk hns hoj hot hoz hpe hpg hpm hpw hqh hqj hqt hqz hre hrk hrs hry hsh hsn hsp hsv hta htg htq hty huv hva hvw hvy hwp hwt hxa hxk hyn hyv hzm hzq hzs i-b i-h i-j i-p i-t iak ias ibd ibv ick icq ics idd idj idt idv iee ieg iem iew ifj ifn igk igm ihb ihd ihn ihp ihz iis iiw iiy ijb ijj ijz ike ikk ikm iky iln ilv ilz ime inh inj int inv ioa ioe iok ioq ioy ipd iph ipt ipz iqg iqs iqw irj irv ise itb ith itt itz iua iuw ivd ivv iwe iwk iwy ixb ixd ixj ixt iya iyg iyk iyq izt j-g j-q j-s jad jan jap jbe jbg jby jcv jdm jds jeh jez jfe jfg jfy jgb jgh jgj jgt jha jhk jhq jhw jid jih jin jip jiz jja jjm jjq jjw jkb jkd jkp jkt jlg jly jmb jmh jna jne jnm jns jnw jod joh jov jpa jpe jps jqd jqh jqj jrm jrq jsn jst jsz jtk jtw juj jup jut juv juz jvq jvw jwh jwp jwv jwz jxk jxm jxy jza jzq jzs jzy k-t kag kam kaw kbh kbn kbp kbt kca kck kcq kcw kdt keg kem keq key kfj kga kgk kgm kgw kgy khb khh kia kig kik kiy kjb kjd kjh kjv kka kkm klj klt klz kmg kmq kms knv knz koe kog kos kow kpj kpp kqw krh krp krv kse ksg ksk ktd ktn ktv kuk kum kuw kvj kvn kvp kwa kwg kww kxb kxj kxn kxv kxz kye kym kys kyy kzj kzp kzt kzz l-e l-m lad lah lba lbe lbq lbs lcb lch lcj lct lde ldg ldk led lej lfm lfs lfw lgd lgn lgz lhe lhg lih lij lip lit liv ljk ljw ljy lkd lkn lkv lls lmd lmj lna lng lnk lny lod loh lot lpa lpg lps lpw lqb lqn lqt lre lrg lrw lsp lst lsv lte ltw lud luh luv luz lva lvg lwb lwh lwv lxa lxg lxq lxw lxy lyh lyj lyn lyp lzk lzm lzq lzw m-b m-n m-t mag maq mbb mbh mbp mbt mdb mdp mea meg mek meq mes mfd mfj mfv mgk mgm mgw mhd mhz mia mim mis miw mjb mjt mjv mkg mkm mkq mlb mlj mlp mma mme mmk mmw mnb mnd mnp moa moe mos moy mpn mpt mpv mqe mqm mrd mrj msq mss mtt mtv muq muw muy mvh mvt mvv mwa mwe mwm mxh mxn mxp mxz myg myk myq myy mzb mzn n-e n-q naj nan nat naz nbg nbk nbm ncb ncn ncp ncz ndg ndq nds ndw neb nep nfa nfw ngd nhe nhg nhk nid nih nij nin nja njk njw njy nkj nkz nla nmb nmj nne nnm nnq nnw nob nop not npa npm nps npy nqb nqv nqz nrq nrs nsd nsj nsn nst ntg nty nuh nup nuz nwd nwj nwt nwz nxe nxg nxm nyb nyh nyj nyv nza o-b o-d o-n o-v oak oaq oay obd obn ock odd odn odp odz oea oem oeq oew ofp oft ofv ogg ogy ohh ohj oht ohv ohz ois ojh okg okk oks oky olb oln olt oma omm omy ond onh onp ook oom opb opp opz oqe oqq orb orp orv orz oss osw oth otn otp otv oua ouq ouy ovt ovv oww oxd oxj oxn oyg oyk oyw ozt p-m p-q p-y pah paj paz pba pbm pby pde pdg pdk pdq peb peh pen pev pfa pfe pfg pfm pgj pgn phg phq phw pib pip pit piz pje pjg pjs pjy pkh pkj pkt pkz pls plw pmv pmz pna png pob pod ppa ppe ppk ppm ppq ppw pqt pqz prg prk prm pst psz ptg ptw puh puj put puv pve pvk pvs pvw pwd pwp pxk pxq pyd pyh pzg pzk pzm pzy q-h q-p q-t qaa qam qaq qbd qbj qbz qce qcm qcq qcw qdb qdj qdp qdz qek qem qes qey qfn qfv qga qgg qgs qhb qhd qhj qia qie qik qiq qiw qjh qjz qkg qkm qkw qld qlv qlz qmm qms qnj qnt qoa qok qow qoy qpd qpp qqa qrj qrn qrt qsa qse qsk qsm qsq qth qtt qtz qug qum qus quw qvn qvp qvt qvv qws qww qxb qxh qxv qyy qzd qzh qzn qzz r-e r-y rab raj ran rav rba rbg rbk rcn rcp rcz rdk rds reb rej rfg rfm rfy rgb rgp rgt rgz rha rib rip rje rjg rjs rjy rkb rkv rle rlk rlq rlw rmd rmn rmz rnm rnw roj roz rpm rpw rqj rqp rre rrk rrs rry rsn rtg rtq rts rty rub rud ruh rut ruv rve rvg rvm rwh rwn rwp rwt rxk rxs ryb ryj rze rzg rzq s-h s-v s-z saa sae saw say sbb sbh sbp sbz sca sdd sdh sek sem sew sey sfp sft sgk sgq shd shn shp sht sim sjv ska ske skk sky slb slv sme sms snn snt snv soy spj spt sqk sqm sqq srd srj sse ssw ssy stj stp stt sua sue sum sus svb svd svp swg swq sxd sxt syg syk syq syw syy szd szh szj t-k t-m tan tat tav taz tbe tbs tbw tch tcv tdk tdy teb teh tep tev tez tfe tfk tfq tfy tgb tgj tgn tha thq thy tid tih tit tja tjq tjs tkb tkj tkn tkt tls tly tmh tmp tmt tmz tnk tny tpa tpe tps tqn tqv trg trk trq try tsh tsn tta ttk ttq tts tub tun tuz tvm tvs tvy twp twz txe txm tyd tyh tyn typ tyv tze tzg tzq tzy u-d u-j u-t u-v uam uaw uay ubj ubn ubt uca uck ucw udj udv udz ueg ueq uew ufb ufv ufz ugm uhb uhp uhz uig uiq ujb ujd ujv uka ukm ukw ulh ulj uln ulp uma umg umk ums umw uom uoq uos uow uoy uph upt upz uqe uqs uqw urb urh urn urv usa utj uua uue uuk uum uuy uvd uvj uvp uvt uwg uxb uxn uxp uyg uyq uyw uzv v-s v-w v-y vab vad vah vav vaz vbe vbk vbs vch vct vcv vej ven vep vet vfq vfw vgb vgd vgv vgz vhm vhs vit vjk vjy vkd vkn vkz vla vlg vls vmv vna vne vnk vnq vod voh voj vpg vpk vpq vpw vqv vre vrw vsb vsj vsp vsv vty vub vun vuz vva vvq vvs vvy vwb vwn vxe vxg vxm vxq vyp vza vzg vzs vzw w-t waq wbb wbh wbj wbv wcw wdd wdh wdn wdz wea wes wey wfb wfh wfn wgg wgw wgy whd whj wia wik wiq wis wiw wjd wjj wjp wkm wlb wlh wlp wlz wme wms wnn wnv wok woq wos wpd wph wpj wqe wqm wrd wsk wsm wss wtj wtn wtt wtz wug wuq wuy wvp wvv wvz wwa wwe wwm wxb wxd wxp wya wyg wyy wzb wzh wzn wzt wzv x-a x-m x-w xap xba xbs xbw xcb xcd xct xcv xde xds xdw xez xfa xfk xfw xfy xgv xha xhq xhy xih xij xiv xjq xjw xjy xkn xlg xlq xls xmd xmp xng xnq xob xoh xoj xot xov xpa xpk xqb xqd xqp xqv xqz xre xrg xsd xte xtg xtk xtm xtw xty xun xuz xvg xwb xwd xwj xwn xwp xwz xxe xxy xyj xyt xza xzm xzs xzy y-d y-h y-z yaa yae yaq ybh ybj ybv yca yce ycg ycw ydh ydt yeg yek yes yfj yfn yfz ygm ygs ygy yhb yhj yhp yht yim yiy yjh yjv yjz yka ykq yks yld ymg ymk ymq ynn yog ypd ypn ypv yqg yqq yrb yrh yrt yse ysk yss yth ytv yua yue yuk yvt ywm yww yxz yyk yym yyq yys yzt z-e z-s z-y zat zba zbe zbw zcb zcp zdg zdk zdq zds zdy zfe zfw zfy zgn zgt zhk zhm zij zin zip ziv zjg zjm zjy zkh zkp zkv zlk zlw zmd zmn zna zon zot zov zpa zpe zpq zqd zqh zqj zqn zqp zqt zra zrg zrq zrw zsb zsd zsj zsp zsv ztg ztm zuj zut zuv zve zvk zvw zwb zwh zwv zxa zxg zze zzy

[efyfabmr] map coloring the Voronoi diagram of equally spaced points on a sphere

pick one of the many methods for placing N "equally spaced" points on a sphere (e.g., Thomson problem, Tammes problem), compute the Voronoi partition, then map color, i.e., avoid adjacent regions of the same color.  (Lloyd's algorithm conveniently uses Voronoi to produce equally spaced points.)

4 colors suffice.  such a coloring might be pretty.  I suspect there will not be adjacent Voronoi regions with very short borders.  (maximizing the minimum Voronoi border segment could be another "equally spaced" metric.)

or, equally spaced points on the surface of any shape.  (the surface needs to have a definition for distance between any two points, a metric.  this might be related to a geodesic.)  if the shape is not topologically a sphere, then more than 4 colors might be required.  amazingly, the sufficient number is known for any number of holes in the donut (Heawood conjecture, no longer a conjecture, according to Wikipedia); the case of zero holes (the sphere or equivalently the plane) was the last to be proven.

colors = floor((7 + sqrt(1 + (48 * holes)))/2)

(there is a generalization of the formula that works if the surface has cross caps (real projective planes), e.g., Klein bottle.  such surfaces always self intersect in 3D space.  the classification theorem of surfaces then says that donut holes and cross caps are enough to topologically define any closed surface.)

is there a polynomial time algorithm that colors with the sufficient number of colors any map on a surface of any genus?

are random such coloring problems, the Voronoi diagrams of roughly equally spaced points, relatively easy to color?

how often can such maps on a sphere be 3-colored?  the regular hexagon tiling can be 3-colored.

there may be many ways to color the Voronoi partition, many more than just the 24 = 4! ways from permuting 4 colors.  how often does this happen?  if it does happen, how can we pick one of the colorings uniformly randomly?

[riqxgwhu] ordering a deck of cards in ways that makes sense

suit major, rank major (2 possibilities)

ordering of suits (4! = 24)

king high, ace high (2)

low instead of high (i.e., reverse the ranks) (2)

total number of ways = 2 * 24 * 2 * 2 = 192

a deck of cards ordered in any of these ways will not arouse suspicion as encoding information.  or, given a deck of cards suspected of encoding information in their ordering, these are possibilities of the "start" ordering.

cf 52! ~= 192^29.7 .

next, consider adding two distinct jokers, not breaking up the main body of cards.  multiply by 3! = 6 yielding 1152.  10 bits or 3 digits.

[hgtrowvn] reciprocals of odd numbers mod 2^n

odd numbers have multiplicative inverses modulo 2^n (even numbers do not).

? for(n=1, 8, print1(2^n,":"); for(j=1, 2^(n-1), i=2*j-1; print1(" ",lift(Mod(i,2^n)^-1))); print())

for example, in 4th line below, the reciprocals of 1 3 5 7 9 11 13 15 modulo 16 are 1 11 13 7 9 3 5 15 respectively.  the product of each number multiplied by its reciprocal is a number of the form 16N+1.

2: 1

4: 1 3

8: 1 3 5 7

16: 1 11 13 7 9 3 5 15

32: 1 11 13 23 25 3 5 15 17 27 29 7 9 19 21 31

64: 1 43 13 55 57 35 5 47 49 27 61 39 41 19 53 31 33 11 45 23 25 3 37 15 17 59 29 7 9 51 21 63

128: 1 43 77 55 57 35 69 111 113 27 61 39 41 19 53 95 97 11 45 23 25 3 37 79 81 123 29 7 9 115 21 63 65 107 13 119 121 99 5 47 49 91 125 103 105 83 117 31 33 75 109 87 89 67 101 15 17 59 93 71 73 51 85 127

256: 1 171 205 183 57 163 197 239 241 27 61 167 41 19 53 223 225 139 173 151 25 131 165 207 209 251 29 135 9 243 21 191 193 107 141 119 249 99 133 175 177 219 253 103 233 211 245 159 161 75 109 87 217 67 101 143 145 187 221 71 201 179 213 127 129 43 77 55 185 35 69 111 113 155 189 39 169 147 181 95 97 11 45 23 153 3 37 79 81 123 157 7 137 115 149 63 65 235 13 247 121 227 5 47 49 91 125 231 105 83 117 31 33 203 237 215 89 195 229 15 17 59 93 199 73 51 85 255

they look quite random, but there are some patterns, like some early (e.g., 11, 13, 57) and late numbers (e.g., 51, 85) persisting through several exponents.

the randomness is reminiscent of multiplicative inverse modulo a prime number.  however, prime numbers and powers of 2 are about as different as numbers can be.

the reciprocal of a reciprocal is itself, so most numbers pair with another (two-cycle).  however, 1, (2^(n-1) - 1), (2^(n-1) + 1), and (2^n - 1) (the last one equivalent to -1) are always their own inverses (one-cycle).

previously: it is possible to set up a Galois field of order 2^n so that all nonzero elements (not just the odd elements) have reciprocals.  the reduction operation becomes more complicated than integer modulo 2^n.

[hwsolprj] the 3D actual reality experience

inspired by "___: the 3D virtual reality experience"

[acrvinwj] pi vs 2pi in binary

in base 2, the battle between pi and 2pi (tau) is over where to put the decimal point:

1.10010010000111111011010... = pi/2
11.0010010000111111011010... = pi
110.010010000111111011010... = 2pi

[blyqokgn] simultaneously define record type and data

we propose a Haskell syntax extension which may be useful when a record type has very few data values of that type, perhaps just one, e.g., the Singleton design pattern.

introduce the keyword DEFINERECORD:

singletonrecord :: Recordtype;
singletonrecord = DEFINERECORD RecordType RecordConstructor { john :: Int = 1, paul :: String = "bass", george :: Bool = True, ringo :: Float = 1.0};

the benefit of this syntax is that the field types and their corresponding values get defined next to each other.  future code changes to type and value will happen at the same place.  there is less danger of accidentally leaving a field uninitialized.

also, the field labels are each written exactly once (Don't Repeat Yourself), in contrast to the current method (below), defining the data type then defining the singleton record using record syntax, which requires typing each field label twice.  although you can optionally put type annotations on field values so that field, value, and type are next to each other when defining the singleton, it feels like even more Repeating Yourself.

data RecordType = RecordConstructor { john :: Int, paul :: String, george :: Bool, ringo :: Float };
singletonrecord :: Recordtype;
singletonrecord = RecordConstructor { john = 1 :: Int, paul = "bass" :: String, george = True :: Bool, ringo = 1 :: Float};

the proposed syntax cannot be used if RecordType has multiple constructors.  (because there can only be one constructor, also consider simpler syntax which restricts the constructor to be the same as that of the type.)

if you have nested records, the syntax can define inner record types "in place" as well.

singletonrecord :: Recordtype;
singletonrecord = DEFINERECORD RecordType RecordConstructor { john :: Int = 1, paul :: String = "bass", george :: Bool = True, ringo = DEFINERECORD DrumType DrumConstructor { snare :: Double = 1.0, cymbal :: String = "crash" } };

this might be a nice feature to combine with Data.Default .

slight variation: record types can be unnamed (anonymous), but have named accessor functions (named fields).  introduce the keyword UNNAMEDRECORD, which stands for both type and constructor.

f1 :: UNNAMEDRECORD;
f1 = UNNAMEDRECORD { john :: String = "guitar", paul :: String = "bass", george :: String = "guitar", ringo = UNNAMEDRECORD { snare :: Double = 1.0, cymbal :: String = "crash" } };

f2 :: UNNAMEDRECORD;
f2 = UNNAMEDRECORD { capital :: String = "london", home :: String = "liverpool" };

g :: String;
g = let
{ v1 :: UNNAMEDRECORD
; v1 = f1
; v2 :: UNNAMEDRECORD
; v2 = f2
} in cymbal (ringo v1) ++ home v2;
-- returns "crashliverpool"

this is better than returning multiple values through tuple syntax because components get named, both when creating and extracting.  using names seems less error-prone than extracting tuple components by position:

g = let { v1 = f1 ; v2 = f2 } in (case v1 of {(_,_,_, (_,x) )->x}) ++ snd v2

open question: if we use DEFINERECORD or UNNAMEDRECORD inside a let or where, should the type name and accessor functions escape the let and become visible in the global scope?  perhaps explicitly mark things for export from the let (requires more new syntax).

more sophistication (and complexity) possible: lenses, record wildcards and puns, etc.  type inference probably becomes more difficult.

related work by Alexander Thiemann: SuperRecord anonymous records.

although we propose this extension for Haskell, it seems a nice feature to have in any programming language.