Krill are filter feeders. True to its namesake, krill
filters feeds. It is not picky about its diet, and will happily consume RSS, Atom, CDF and even Twitter feeds (no credentials required!). It aggregates feed items from all sources you specify, filters out those that interest you, and displays them
Krill are filter feeders. True to its namesake, krill
filters feeds. It is not picky about its diet, and will happily consume RSS, Atom, CDF and even Twitter feeds (no credentials required!). It aggregates feed items from all sources you specify, filters out those that interest you, and displays them as a live stream of clean, legible command line output.
krill
is beautifully minimal. krill
is extremely easy to set up and use, and runs anywhere Python runs. krill
is a refreshingly different way of consuming news and updates from anywhere on the web. krill
is the hacker's way of keeping up with the world.
krill
requires Python 2.7+/3.2+. If you have the pip package manager, all you need to do is run
pip install krill
either as a superuser or from a virtualenv environment.
krill [-h] [-s URL [URL ...]] [-S FILE] [-f REGEX [REGEX ...]]
[-F FILE] [-u SECONDS]
-s URL [URL ...], --sources URL [URL ...]
URLs to pull data from
-S FILE, --sources-file FILE
file from which to load source URLs (OPML format
assumed if filename ends with ".opml")
-f REGEX [REGEX ...], --filters REGEX [REGEX ...]
patterns used to select feed items to print
-F FILE, --filters-file FILE
file from which to load filter patterns
-u SECONDS, --update-interval SECONDS
time between successive feed updates (default: 300
seconds, 0 for single pull only)
krill -s "https://twitter.com/nasa" -f "new ?horizons"
will follow NASA's Twitter stream, printing only tweets that mention the New Horizons probe.
krill
automatically determines whether to treat a web document as a Twitter or an XML feed. If multiple sources and/or filters are loaded from a file with the -S
and -F
tags, each must be on a separate line (except if the sources file uses the OPML format, in which case all xmlUrl
attributes are loaded). Empty lines and lines starting with #
(comments) are ignored.
Any URL format accepted by the Requests library is supported. In particular, feeds requiring (basic) HTTP authentication can be accessed by supplying credentials in the URL string with https://user:password@example.com/feed
.
Inline and file specifications may be combined freely. If more than one filter is given, items matching any of the filters are printed. If no filter is given, all items are printed.
Cover image: Uwe Kils (Wikimedia Commons, CC-BY-SA)
]]>]]>Note:
To make this work, your system needs three things:
- Bash 4+
- Python (with
python
defaulting to Python 2)- Tkinter
The first two are fulfilled out of the box on most modern Linux distributions, the last two are default in OS X. Therefore, on Linux you need to install Tkinter,
Note:
To make this work, your system needs three things:
- Bash 4+
- Python (with
python
defaulting to Python 2)- Tkinter
The first two are fulfilled out of the box on most modern Linux distributions, the last two are default in OS X. Therefore, on Linux you need to install Tkinter, while on OS X a recent version of Bash has to be installed (e.g. via Homebrew) because OS X still ships with Bash 3.2.
Note 2:
I am well aware that toucans have nothing to do with the content of this post, but I could not think of a tangible metaphor for shell scripting and I just love how these birds look :)
The ubiquitous and venerable Bash can be quite a flexible tool once one gets past its idiosyncratic scripting environment and many quirks. As an example of what is possible, add the following to your .bashrc
(Linux) / .bash_profile
(OS X):
select_files() {
local files="$(python -c 'import Tkinter, tkFileDialog; Tkinter.Tk().withdraw(); print(" ".join(map(lambda x: "'"'"'"+x+"'"'"'", tkFileDialog.askopenfilename(multiple=1))))')"
READLINE_LINE="${READLINE_LINE:0:READLINE_POINT}$files${READLINE_LINE:READLINE_POINT}"
READLINE_POINT=$((READLINE_POINT + ${#files}))
}
bind -x '"\C-g":select_files'
From now on, whenever you are in a graphical terminal emulator typing a command, press Ctrl+G at any time to bring up a system file picker dialog supporting multiple selections which will insert the full paths of all files you picked right back into the command line you were working on! Python does the heavy lifting here, while Bash's readline features provide the glue that ties everything together. If X11 forwarding over SSH is enabled, this might even work for remote systems (not tested yet).
Note that changing the keyboard shortcut to something else is not as straightforward as it may seem. Many other key combinations can not be bound with the -x
flag although workarounds do exist. Welcome to the weird and wonderful world of shell scripting...
Cover image: Olaf Oliviero Riemer (Wikimedia Commons, CC-BY-SA)
]]>Two years after its original introduction, and following a year-long period of mostly stagnant development, I am officially discontinuing work on the Final Term project today.
In its relatively short lifetime, Final Term has drawn its share of attention. On GitHub, it is more popular than all other Vala projects
]]>Two years after its original introduction, and following a year-long period of mostly stagnant development, I am officially discontinuing work on the Final Term project today.
In its relatively short lifetime, Final Term has drawn its share of attention. On GitHub, it is more popular than all other Vala projects combined and indeed seems to be the most popular desktop program running exclusively on Linux. It has been on the front page of Hacker News and the number one trending GitHub project back in 2013. It netted me an interview with Linux Magazine.
Since then, a lot has happened. A surprising number of users stepped forward to contribute code and feedback, creating new features, fleshing out infrastructure and fixing problems I couldn't have identified by myself in a hundred years. Engaging with community contributors has been a very motivating experience, and kept my own efforts alive for quite a while.
Despite the wonderful input that has helped Final Term become what it is today, I have decided that the time has come for me to move on. There are two reasons for this; the first is personal, the second technological in nature.
You've heard it a thousand times before, but then it is the main reason why open source projects die: Final Term is a personal, private project, unaffiliated with and unsupported by any commercial entity or interest. As such, it is fueled by whatever spare time its contributors choose to invest in it. Since my spare time is limited, I have to focus it on whatever idea interests me the most, and Final Term is no longer that idea.
I wish there were more to say here, but there really isn't. The truth is dead simple: My heart is not in this project anymore, and that effectively means the project has come to an end unless someone else continues it. Which brings me to ...
This is actually the main reason, and has dramatically reduced my motivation to continue developing the project. Technological changes in the past two years have been mostly to Final Term's disadvantage: They both diminish its potential usefulness and make sustainable development using the existing platform very unlikely.
The biggest culprit is certainly Mx, a Clutter-based widget toolkit that much of Final Term's UI code relies on. Originally intended for corporate-backed megaprojects like MeeGo, Mx seemed like a rock-solid choice when Final Term was conceived. Today, things look quite different: Mx is dead, its last commit dating from 2013. Since Mx still has numerous bugs that affect Final Term, this bodes ill for future development, and there seems to be no obvious fix except rewriting everything on top of another (which?) framework.
At the same time, the programming world itself has been transformed in a way that calls into question nearly every technology choice behind Final Term.
A highly visible aspect of this transformation is the continuing advance of the Mac as the platform of choice for many professional software engineers. While I still do not feel OS X is as natural an environment for programming and server administration as Linux, it is becoming increasingly obvious that most professionals disagree. No one in their right mind would see OS X support as an afterthought when starting a project like Final Term today, and perhaps the idea was naive even back then, as desktop Linux adoption has (predictably) disappointed expectations once again. With Apple's proprietary platform diverging from Linux more and more, there appears to be no clean way to get Final Term to work on OS X, despite strong community interest and a brave attempt at a Homebrew build. As Final Term misses out on the ever-growing crowd of Mac-based developers, it becomes more and more a niche product instead of the mainstream product it was intended to be.
Other developers have since shown how to do multi-platform support properly. The advent of Electron/Atom Shell, backed by open source trendsetter GitHub, has been met with much enthusiasm as it promises (and delivers!) a clean, rapidly advancing web-based environment that works on Linux, OS X and even Windows with zero porting effort required. In this goal, it is arguably much more successful than previous attempts such as node-webkit, and convincingly demonstrates that web-based desktop software, performance and portability are not mutually exclusive. I fully expect to see an Electron-based terminal emulator emerge very soon, which is then bound to rapidly overtake Final Term in adoption, ease of development and number of contributors. It is now clear that TermKit, originally announced in 2011, was ahead of its time not only with its UI ideas but also with its choice of platform, and would no doubt quickly reach production-level maturity if released today as an Electron-based multi-platform application.
To summarize, Final Term has regrettably saddled some dead horses, and in doing so has missed a big train that has now left the station.
Not much is left to salvage from Final Term's code base, but I do hope that the ideas behind the project will not all die with it. Context-aware terminal emulation has great potential to simplify common terminal tasks, and a break from at least some of the shackles imposed by decades-old text interfaces is long overdue. Traditional text shells are most likely here to stay for another 10-20 years before at last we can transition to TermKit-like terminals operating on structured data, but in the meanwhile, we should make sure those shells are presented and enhanced by modern graphical user interfaces rather than being stuck in the past forever.
That being said, I realize not all may agree with my reasons for giving up Final Term and some may wish to continue working on it. If that is the case, I am willing to officially hand over the project to anyone who brings enough commitment and experience to convince me that they can pull it off. Don't hesitate to contact me if you would like to become Final Term's official maintainer.
I am very grateful to the many people who have demonstrated their enthusiasm for Final Term in the past two years by constantly reminding me to work on the project, and especially to those who have chosen to advance the project with code contributions. It is my sincere hope that they will understand and accept my decision, and not feel that their work has been in vain.
Update: George Nachman, author of iTerm2, has informed me that some of Final Term's spirit might soon see new life in an upcoming version of iTerm2! (Note that while the ideas are similar, their implementation is not and Final Term's Termlets will likely not work in iTerm2). iTerm2 is certainly the most advanced terminal emulator available today and George's work has been the gold standard of text interfaces for years. It thrills me to know that the effort to integrate terminal and shell will not die with Final Term.
Cover image: Tom Thiel (Wikimedia Commons, CC-BY)
]]>A modest proposal. The idea is probably not new, but I find it very sensible indeed. Surely some basic knowledge about candidates can be expected from someone who wants to participate in deciding the political fate of a society!
Yes, this may prevent some people from being able to cast
]]>A modest proposal. The idea is probably not new, but I find it very sensible indeed. Surely some basic knowledge about candidates can be expected from someone who wants to participate in deciding the political fate of a society!
Yes, this may prevent some people from being able to cast a valid vote. No, this is not an unacceptable exclusion, any more than excluding toddlers from voting is. Seriously, if you have no idea what you are voting for, what are you doing with a ballot in your hand?
Cover image: "The Mascot", New Orleans (Wikimedia Commons, Public domain)
]]>The previously introduced software Sequencer identifies number sequences algorithmically. The On-Line Encyclopedia of Integer Sequences (OEIS) is by far the largest collection of curated number sequences available today. It therefore seems natural to employ Sequencer in a quest to uncover patterns that have been previously overlooked, by virtue of sheer
]]>The previously introduced software Sequencer identifies number sequences algorithmically. The On-Line Encyclopedia of Integer Sequences (OEIS) is by far the largest collection of curated number sequences available today. It therefore seems natural to employ Sequencer in a quest to uncover patterns that have been previously overlooked, by virtue of sheer brute force computing power brought down upon even the most "uninteresting" sequences.
The idea of using software to automatically identify patterns in the OEIS database is not new. Hieu Nguyen's 2012 talk "Data Mining the Online Encyclopedia of Integer Sequences for New Identities" describes a system that applies various transformations to sequences and attempts to correlate the results to experimentally discover candidate identities involving multiple sequences. At least one attempt has also been made before to find sequences that satisfy recurrence relations: Tanya Khovanova maintains a page with the results of such a search conducted in 2007, and in particular has identified some sequences whose elements as given by the OEIS pass recurrence tests, but are known to break that pattern at a later point not covered by the numerical data. The OEIS Wiki itself also has a list of sequences which agree for a long time but are nonetheless different. These examples serve as a reminder of the age-old wisdom that even mountains of numerical "evidence" can be misleading, which is why all results presented here should be taken with caution.
Because the goal was to find unknown formulas, OEIS entries possessing a "formula" field were excluded from the search, leaving only those without an associated formula. As of 8th March 2015, there were 156,592 such entries in the OEIS (the complete list was kindly provided to me by Charles Greathouse).
A total of around 650 CPU hours @ 3.2 GHz were spent running Sequencer on those entries, equivalent to 15 CPU seconds per entry on average. Unfortunately, it quickly turned out that absence of the "formula" field is an unreliable indicator for the absence of a formula in an entry: Formulas are often found in the title of the entry (e.g. A215137) or in the "comments" field (e.g. A203400). Nevertheless, exclusion of entries with known formulas prevented the rediscovery of thousands of redundant closed-form expressions which would have made manually examining the results very tedious.
All results may be reproduced by running the Sequencer JAR as follows:
java -jar sequencer.jar -r 1 -n -t [numbers]
The full search output can be found here. A quick glance shows that most of the formulas found are in fact recurrence relations. This is because Sequencer constructs expressions going from simple to complex, and the complexity of closed-form expressions can often be "tucked away" in the initial values of a recurrence, which are simply pulled from the input numbers. At the risk of waxing philosophical here, there seems to be a deeper computational truth in the sense that recurrence relations are more "elementary" descriptions of number sequences than index-based ones.
Note that Sequencer always uses one-based indexing, i.e. the formulas consider $a_1$ to be the first element of the sequence, irrespective of the value of the OEIS entry's "offset" field.
Out of 156,592 entries examined, Sequencer identified closed-form relations for 1318 of them. The vast majority of these results are immediately recognized as useless, falling into three broad categories:
The remaining 107 cases contain a mixture of moderately interesting and marginally interesting candidate formulas, a selection of which is presented here:
Each of the following conjectures holds for all elements of the given sequence as provided by the OEIS.
Superpositions of cycles of order $n$ of the groups $S_2$ and $D_n$.
1, 2, 4, 10, 28, 130, ...
$$
a_n = a_{n-2} \, (a_{n-2}+3)
$$
$T(n,n+1) + T(n,n+2) + \dots + T(n,2n)$, $T$ given by A027960.
1, 5, 14, 35, 81, 180, 389, 825, 1726, 3575, 7349, 15020, 30561, 61965, 125294, 252795, 509161, 1024100, 2057549, 4130225, 8284926, 16609455, 33282989, 66669660, 133507081, 267285605, 535010414, 1070731475, 2142612801, ...
$$
a_n = a_{n-2} + a_{n-1} + 2^n
$$
This recurrence can be solved algebraically and is probably related/equivalent to the formula from A027974.
Numbers $n$ such that $n^8 \equiv 1 \pmod{9^3}$.
1, 728, 730, 1457, 1459, 2186, 2188, 2915, 2917, 3644, 3646, 4373, 4375, 5102, 5104, 5831, 5833, 6560, 6562, 7289, 7291, 8018, 8020, 8747, 8749, 9476, 9478, 10205, 10207, 10934, 10936, 11663, 11665, 12392, 12394, 13121, 13123, 13850, 13852, ...
$$
a_n = \frac{1}{4} \, (1458 n - 729 + (-1)^n \times 725)
$$
It is clear that $x$ is in A056084 iff $x + 9^3$ is, so (once you verify that $1$ and $728$ are the only entries $< 9^3$) the conjectured formula is certainly true.
"Catapolyoctagons (see Cyvin et al. for precise definition)."
0, 2, 12, 62, 312, ...
An entry without details (apparently motivated by chemistry), but it might be that
$$
a_n = \frac{1}{10} \, (5^n - 5)
$$
Number of $n$-celled polyominoes, where the cells are $1 \times 2$ rectangles with one edge of length $2$ replaced by a curved arc that either sags inwards or bulges outwards, subject to some restrictions.
1, 2, 10, 84, ...
$$
a_n = C_n \, (n - 1)!
$$
where $C_n$ is the $n$th Catalan number.
Given that there are only four known elements, any conjecture based on numerical evidence alone is daring indeed, but this looks like a "natural" identity for a combinatorial process.
Numbers $n$ such that both $n$ and $n+1$ have at least one divisor of the form $p^e$ with $p\le e$, $p$ prime.
27, 80, 135, 188, 243, 296, 351, 404, 459, 512, 567, 620, 675, 728, 783, 836, 891, 944, 999, 1052, 1107, 1160, 1215, 1268, 1323, 1376, 1431, 1484, 1539, 1592, 1647, 1700, 1755, 1808, 1863, 1916, 1971, 2024, 2079, 2132, 2187, 2240, 2295, 2348, 2403, 2456, ...
$$
a_n = 54n - \frac{1}{2} \, (55 + (-1)^n)
$$
The conjecture for A129254 will match little more than the values listed – the pattern will break as soon as we start to reach [neighbours of] multiples of $5^5$, $3124$ being the first example.
Exchange successive pairs of terms of A000051. (i.e. $2^n + 1$)
3, 2, 9, 5, 33, 17, 129, 65, 513, 257, 2049, 1025, 8193, 4097, 32769, 16385, ...
$$
a_n = 2^{n-3} \, (5 - 3 \times (-1)^n) + 1
$$
Observe that
$$
4 \, (a_n - 1) + 1 = a_{n+2}
$$
and solve the recurrence relation.
One-third of the number of $n \times n$ nonnegative integer arrays with every $3 \times 3$ subblock summing to $1$.
3, 7, 11, 15, 27, 39, 51, 87, 123, 159, 267, 375, 483, 807, 1131, 1455, 2427, 3399, 4371, 7287, 10203, 13119, 21867, 30615, ...
$$
a_n = 3 \, (a_{n-3} + 2)
$$
"Number of sets (in the Hausdorff metric geometry) at each location between two sets defining a polygonal configuration consisting of two $4$-gonal polygonal components chained with string components of length $l$ as $l$ varies."
113, 176, 289, 465, 754, 1219, 1973, 3192, 5165, 8357, ...
$$
a_n = \frac{1}{2} \, (163 \, F_n + 63 \, L_n)
$$
where $F_n$ is the $n$th Fibonacci number and $L_n$ is the $n$th Lucas number.
I must admit that I have absolutely no clue what the definition actually means, or what it is useful for. However, the OEIS entry includes a very complex Maple program for computing the sequence, which could be dramatically simplified if the conjecture were true.
"A conjectured sequence of bud numbers for eucalyptus flowers."
1, 3, 7, 13, 21, 31, ...
$$
a_n = n^2 - n + 1
$$
Biological processes usually don't precisely follow the mathematics drawn up to describe them. Whether or not this formula is an actual pattern I cannot even speculate about.
Adjusted joint rank sequence of $(f(i))$ and $(g(j))$ with $f(i)$ after $g(j)$ when $f(i)=g(j)$, where $f(i)=3i$ and $g(j)=j(j+1)/2$ (triangular number). Complement of A186357.
1, 2, 4, 7, 9, 12, 16, 19, 23, 28, 32, 37, 43, 48, 54, 61, 67, 74, 82, 89, 97, 106, 114, 123, 133, 142, 152, 163, 173, 184, 196, 207, 219, 232, 244, 257, 271, 284, 298, 313, 327, 342, 358, 373, 389, 406, 422, 439, 457, 474, 492, 511, 529, 548, 568, 587, 607, 628, 648, 669, 691, 712, 734, 757, 779, 802, 826, 849, 873, 898, 922, 947, 973, 998, 1024, 1051, 1077, 1104, 1132, 1159, 1187, 1216, 1244, 1273, 1303, 1332, 1362, 1393, 1423, 1454, ...
$$
a_n = \frac{1}{18} \, \left( 3n^2 + 21n - 8 \, \sin \left( \frac{\pi}{6} - \frac{2 \pi n}{3} \right) - 14 \right)
$$
This relatively complex formula is the solution to the recurrence relation
$$
a_n = a_{n-3} + n + 2
$$
which was found by Sequencer, given the initial values from the sequence. A186355 and A186498 appear to satisfy the same recurrence, with different initial values.
Numbers of spanning trees of the barbell graphs. (Should this be "Number of spanning trees ..." instead?)
9, 256, 15625, 1679616, 282475249, 68719476736, 22876792454961, 10000000000000000, 5559917313492231481, 3833759992447475122176, 3211838877954855105157369, 3214199700417740936751087616, 3787675244106352329254150390625, 5192296858534827628530496329220096, 8193465725814765556554001028792218849, 14747559712960682275277163588165279154176, 30034640110980377619945846078500632729311721, 68719476736000000000000000000000000000000000000, ...
$$
a_n = (n+2)^{2n}
$$
Number of $2 \times 2$ matrices with all terms in ${0,1,\dots,n}$ and odd trace.
0, 8, 36, 128, 300, 648, 1176, 2048, 3240, 5000, 7260, 10368, 14196, 19208, 25200, 32768, 41616, 52488, 64980, 80000, 97020, 117128, 139656, 165888, 195000, 228488, 265356, 307328, 353220, 405000, 461280, 524288, 592416, 668168, ...
$$
a_n = n^2 \, \left\lfloor \frac{n^2}{2} \right\rfloor
$$
Note that this formula also implies a formula for A210378 via the observation in the comments section of A210379 that A210379(n)+A210378(n)=(n+1)^4
.
Note that this proof uses the offset $0$ as given in the entry.
The factor $(n+1)^2$ stands for the number of elements at entries $(1,2)$ and $(2,1)$ of the matrix, which do not participate in the trace calculation and thus each can independently take all $n+1$ different values. The factor $\lfloor (n+1)^2/2 \rfloor$ counts number of pairs of elements (indexed $(1,1)$ and $(2,2)$ in the matrix) from $\{0,1,...,n\}$ with odd sum. If $n$ is odd, there are $(n+1)/2$ even and $(n+1)/2$ odd numbers in the set, implying that the number of pairs with odd sum is $$(n+1)/2 \times (n+1)/2 + (n+1)/2 \times (n+1)/2 = (n+1)^2/2 = \lfloor (n+1)^2/2 \rfloor$$ If $n$ is even, there are $(n+2)/2$ even and $n/2$ odd numbers in the set, implying that there are $$(n+2)/2 \times n/2 + n/2 \times (n+2)/2 = n \times (n+2)/2 = \lfloor (n+1)^2/2 \rfloor$$
Numbers $n$ such that $n^2 + 1$ is divisible by a $5$th power.
1068, 2057, 4193, 5182, 7318, 8307, 10443, 11432, 13568, 14557, 16693, 17682, 19818, 20807, 22943, 23932, 26068, 27057, 29193, 30182, 32318, 33307, 35443, 36432, 38568, 39557, 41693, 42682, 44818, 45807, 47943, 48932, 51068, 52057, 54193, 55182, 57318, 58307, ...
$$
a_n = \frac{1}{4} \, (6250 n - 1147 \times (-1)^n - 3125)
$$
Similar formulas exist for A218565 and A218574.
The conjectured formula for A218564 (Numbers $n$ such that $n^2+1$ is divisible by a $5$th power) is wrong. The "period" in the conjectured formula is $5^5$, and the listed sequence terms just not yet reached the next possible fifth power divisor, which is $13^5$. E.g., there is a term $143044$ of A218564 (with $143044^2 + 1$ divisible by $13^5$), which does not fit the proposed formula.
Number of years after which it is possible to have a date falling on same day of the week, but the entire year does not have the same calendar, in the Julian calendar.
5, 23, 33, 51, 61, 79, 89, 107, 117, 135, 145, 163, 173, 191, 201, 219, 229, 247, 257, 275, 285, 303, 313, 331, 341, 359, 369, 387, 397, 415, 425, 443, 453, 471, 481, 499, 509, 527, 537, 555, 565, 583, 593, 611, 621, 639, 649, 667, 677, 695, 705, 723, 733, 751, 761, 779, 789, ...
$$
a_n = 14n + 2 \times (-1)^n - 7
$$
The conjecture about A231002 is more or less explained in the sequence, but incorrectly stated as "the sequence has a period of $28$". What is meant is that the characteristic sequence of these years has a period of $28$, i.e., $n>0$ is in the sequence iff $n+28$ is in the sequence, and since $5$ and $23$ ($\equiv -5 \pmod{28}$) are the only terms $\le 28$, this is the sequence of numbers congruent to $+$/$-$ $5 \pmod{28}$.
Cover image: Alexandre Duret-Lutz (Wikimedia Commons, CC-BY-SA)
]]>Because of their connections with public-key cryptography, trapdoor functions are surrounded by a lot of mystery. While one-way functions (functions that are easy to compute, yet hard to invert) like integer multiplication are familiar and intuitive, the idea of a function that is hard to invert except if one possesses
]]>Because of their connections with public-key cryptography, trapdoor functions are surrounded by a lot of mystery. While one-way functions (functions that are easy to compute, yet hard to invert) like integer multiplication are familiar and intuitive, the idea of a function that is hard to invert except if one possesses some secret, the "trapdoor", seems a more remote possibility. The few such functions suitable for cryptographic purposes that have been found (like the modular exponentiation functions as used by the RSA and Rabin cryptosystems) unsurprisingly require heavy use of number theory to understand and analyze.
The main difficulty with public-key cryptosystems, however, is not the requirement for trapdoor functions, but for injective trapdoor functions (it should be possible to reconstruct the original plaintext after all). As soon as the requirement for injectivity is dropped, trapdoor functions are readily constructed from elementary primitives:
Let $N = pq$ for some prime numbers $p$ and $q$. Define
$$
\begin{align}
g(n) &= n-\lfloor \sqrt{n} \rfloor^2 \\
h(n) &= | \lfloor \sqrt{n} \rfloor - g(n) | \\
f_N(n) &= \frac{g(n)}{2} \left( 1 - \cos \left( 2^{|N \, - \, (g(h(n))+2) \, (h(h(n))+2)|} \, \pi \right) \right)
\end{align}
$$
Then, conditional on the hardness of integer factorization, $f_N$ is a surjective trapdoor function with trapdoor $(p,q)$. Indeed, we have
Theorem: $f_N$ satisfies the following properties:
- For every $m \in \mathbb N$ there exists a (not necessarily unique) $n \in \mathbb N$ such that $f_N(n) = m$.
- For every $m > 0$, finding any $n$ with $f_N(n) = m$ is equivalent to factoring $N$.
What at first glance might appear incomprehensible is actually a rather simple decision procedure, obfuscated through arithmetic.
Observe that $g$ and $h$ induce a surjective map $\mathbb N \rightarrow \mathbb N \times \mathbb N$ (a non-injective inverse pairing function). In other words, $(g(n),h(n))$ runs over all pairs of integers. It follows that $(g(n),g(h(n)),h(h(n)))$ runs over all triples of integers. $f_N$ can thus be rewritten as a function on $\mathbb N^3$:
$$
f_N'(n,m_1,m_2) = \frac{n}{2} \left( 1 - \cos \left( 2^{|N \, - \, (m_1+2) \, (m_2+2)|} \, \pi \right) \right)
$$
Now note that
$$
\frac{1}{2} \left( 1 - \cos \left( 2^{|k|} \, \pi \right) \right) =
\begin{cases}
1 & \text{if} \quad k = 0 \\
0 & \text{otherwise}
\end{cases}
$$
This unmasks the true nature of $f_N'$:
$$
f_N'(n,m_1,m_2) =
\begin{cases}
n & \text{if} \quad (m_1+2) \, (m_2+2) = N \\
0 & \text{otherwise}
\end{cases}
$$
Since the factorization is nontrivial and preimages for any values of $g$ and $h$ are readily found, it follows that knowing the prime factors $p$ and $q$ of $N$ is both necessary and sufficient for making the original function $f_N$ produce any value other than $0$.
Background on non-injective trapdoor functions: Bellare et al.: Many-to-One Trapdoor Functions and Their Relation to Public-Key Cryptosystems
Inspiration for pairing function (simplified): Szudzik: An Elegant Pairing Function
Cover image: English Lock (Wikimedia Commons, CC-BY-SA)
]]>Sequencer identifies number sequences. That is, given a list of numbers like
$$(a_n)_{n\geq 1} = 1,; 2,; 4,; 8,; 16,; 32,; \ldots$$
it finds a formula that generates them, in this case
$$a_n = 2^{n-1}$$
Sequencer employs neither a library of sequences nor a limited set of
]]>Sequencer identifies number sequences. That is, given a list of numbers like
$$(a_n)_{n\geq 1} = 1,; 2,; 4,; 8,; 16,; 32,; \ldots$$
it finds a formula that generates them, in this case
$$a_n = 2^{n-1}$$
Sequencer employs neither a library of sequences nor a limited set of algorithms to find a closed form. Instead, it generates all formulas up to a certain size and then checks them against the provided numbers.
For verification, the system uses a hybrid approach of a fast numerical checker followed by a symbolic verifier powered by the Symja computer algebra system. Coupled with some tricks and heuristics designed to quickly generate potentially interesting formulas, Sequencer can identify sequences with very complex closed forms in a matter of seconds when run on commodity hardware.
Sequencer is capable of finding closed forms that are beyond any existing system like OEIS, Superseeker and Wolfram Alpha. It is particularly strong where recurrence relations or unusual combinations of functions are involved. For example, none of the services mentioned above can currently make sense of the sequence
$$(a_n)_{n\geq 1} = 1,; 1,; 1,; 3,; 5,; 15,; 43,; 273,; \ldots$$
while Sequencer reveals that it satisfies the recurrence relation
$$
\begin{align}
a_1 &= 1 \\
a_2 &= 1 \\
a_3 &= 1 \\
a_n &= a_{n-2}^2+a_{n-1}+a_{n-3}\quad \text{for } n\geq 4
\end{align}
$$
and provides the continuation
$$2137,; 76709,; 4643751,; 5888916569,; 21570312343279,; \ldots$$
For quick access to Sequencer's capabilities from anywhere, I have deployed a web application called SequenceBoss (http://sequenceboss.org).
SequenceBoss invokes Sequencer on the numbers entered (with limited search depth) and renders the result in $\LaTeX$ using MathJax. It has a responsive HTML interface that works well on both desktops and mobile devices and is the easiest way to use Sequencer.
For maximum portability and power, Sequencer is distributed in the form of a JAR that can be run from the command line on any platform with a JRE using the syntax
java -jar sequencer.jar 1 2 3 4 5
Sequencer supports many command line options to fine-tune how searches are performed. As of version 1.5.0, the full list is
-d <value> | --depth <value>
search depth (maximum number of nodes in expression tree) [default: 6]
-r <value> | --results <value>
maximum number of formulas to return, 0 for unlimited [default: 5]. Note that for parallel searches, the order in which formulas are found is not deterministic so limiting the number of search results can lead to unreproducible searches unless the --sequential option is also used.
-p <value> | --predict <value>
number of elements to predict in sequence continuation [default: 5]
-u <value> | --recurrence-depth <value>
maximum number of previous elements to consider for recurrence relations [default: 3]
-c | --no-combinatorics
do not search for combinatorial functions (speeds up search)
-n | --no-number-theory
do not search for number theoretic functions (speeds up search)
-t | --no-transcendentals
do not search for transcendental functions (speeds up search)
-q | --sequential
disable search parallelization (single-threaded search)
-s | --symbolic
skip numerical test (symbolic verification only; slows down search)
-o | --hide-progress
do not output progress while searching
-l | --latex
output LaTeX instead of plain text
Sequencer is not limited to processing integers but can identify sequences consisting of arbitrary Symja expressions (provided they can be evaluated numerically). For example, invoking the program with the arguments 0 1/2 sqrt(3)/2 1
produces
a(n) = Sin(1/6*Pi*(n-1))
Continuation: 1/2*3^(1/2), 1/2, 0, -1/2, (-1/2)*3^(1/2), ...
Note that parentheses in arguments need to be escaped (\(
) when running a program from a shell like bash.
Cover image: Nevit Dilmen (Wikimedia Commons, CC-BY-SA)
]]>quicksafe is a tiny Python script that provides a GUI text editor to edit notes that are then encrypted and stored within the script file itself.
Thus notes encrypted with the system bring their own decryption and editing environment, capable of running anywhere Python/Tk can run, perfect for being
]]>quicksafe is a tiny Python script that provides a GUI text editor to edit notes that are then encrypted and stored within the script file itself.
Thus notes encrypted with the system bring their own decryption and editing environment, capable of running anywhere Python/Tk can run, perfect for being archived, sent by mail or posted on the web.
To use quicksafe, simply download the script, make it executable (chmod +x quicksafe
), create a copy named whatever you want (e.g. My Secret Diary
), and run it. Changes are saved automatically when you close the editor. The first time you close, you will be asked to set a password, which will be required thereafter in order to open the file. To change the password, make a fresh copy of the original quicksafe
script, open it, copy and paste your text into the editor and choose a new password when you close it.
Cover image: Bob Lord (Wikimedia Commons, CC-BY-SA)
]]>This package enables semantic highlighting for JavaScript code in the Atom editor. Identifiers are highlighted in different colors (the same identifier always in the same color) while everything else (like language keywords) is displayed in various shades of gray. This approach runs contrary to classical ideas about syntax highlighting but
]]>This package enables semantic highlighting for JavaScript code in the Atom editor. Identifiers are highlighted in different colors (the same identifier always in the same color) while everything else (like language keywords) is displayed in various shades of gray. This approach runs contrary to classical ideas about syntax highlighting but is rapidly becoming very popular.
In addition to being a useful tool for actual, productive JavaScript coding, the package also demonstrates some techniques that might serve other developers when creating similar packages for other languages:
.cson
grammar fileAcorn is a mature, fast JavaScript parser that is available through npm. Unfortunately, the requirements for an Atom grammar necessitated two customizations:
eval
-based keyword recognition to work around Atom Shell's CSP restrictions (this problem is being tracked in https://github.com/marijnh/acorn/issues/90)As a result, this package ships with a modified version of Acorn, but it would be preferable if those issues could be worked out so that Acorn can be pulled from npm in the future.
Cover image: watashiwani (Wikimedia Commons, CC-BY)
]]>This Sublime Text 2/3 plugin sets the dark theme variant for Sublime's windows on GTK+ 3-based systems that support it, such as recent GNOME distributions.
The result is a much more beautiful Sublime when using dark UI themes because the distracting contrast between title bar and chrome
]]>This Sublime Text 2/3 plugin sets the dark theme variant for Sublime's windows on GTK+ 3-based systems that support it, such as recent GNOME distributions.
The result is a much more beautiful Sublime when using dark UI themes because the distracting contrast between title bar and chrome is eliminated. The window border also becomes dark, making the window blend into the desktop better.
cd
into your Sublime Text packages directory (e.g. .config/sublime-text-2/Packages
)git clone https://github.com/p-e-w/GTKDarkThemeVariantSetter.git
Sublime Text (like most other extensible applications) does not provide hooks into its low-level windowing logic. This plugin demonstrates a technique that nevertheless allows for fine-grained control over windows, provided that standard Linux and X.Org tools are present on the system:
pidof [NAME]
xprop -root _NET_CLIENT_LIST
xprop -id [ID] _NET_WM_PID
xprop -id [ID] -f _GTK_THEME_VARIANT 8u -set _GTK_THEME_VARIANT dark
(some background on this very poorly documented property can be found here and here)Cover image: Luc Viatour (Wikimedia Commons, CC-BY-SA)
]]>I designed this poster for a local political poster competition to highlight what I percieve as the single greatest threat to humanity's welfare:
Forget wars and murder, forget the much-condemned "human greed", forget all conceptions of good and evil: At the end of the day, the
]]>I designed this poster for a local political poster competition to highlight what I percieve as the single greatest threat to humanity's welfare:
Forget wars and murder, forget the much-condemned "human greed", forget all conceptions of good and evil: At the end of the day, the ugly truth is that there are too many of us, no matter how you twist and turn the facts. Sustainable living is not a sustainable idea for a species that outnumbers the next most numerous large animal by a factor of one thousand.
This is not a matter of attitude or technology, it is simply a matter of numbers. No peace efforts, no medical advances and no scientific breakthroughs are going to change the fact that the resources of planet Earth cannot provide for billions of humans at the living standard that many of us have become accustomed to by the turn of the 21st century. Our two options are to expand into space where more resources might be found, or to dramatically reduce the size of the world population from what it is today. Since we are clearly not yet ready to pursue the first option on any significant scale, the global promotion and encouragement of birth control is a must from a humanist perspective – and it is safe to call those that still oppose it not only a threat to progress, but indeed a threat to mankind.
Cover image: Dick DeMarsico (Wikimedia Commons, Public domain)
]]>ranwhen is a Python script that graphically shows in your terminal when your system was running in the past. Have a look:
ranwhen is a Python script that graphically shows in your terminal when your system was running in the past. Have a look:
The above requirements should be fulfilled by default on the majority of modern Linux distributions, where the only thing that needs to be done is usually to install Python 3.
]]>Final Term is a new breed of terminal emulator.
It goes beyond mere emulation and understands what is happening inside the shell it is hosting. This allows it to offer features no other terminal can:
Final Term knows which pieces of terminal output represent filenames, PIDs, web
]]>Final Term is a new breed of terminal emulator.
It goes beyond mere emulation and understands what is happening inside the shell it is hosting. This allows it to offer features no other terminal can:
Final Term knows which pieces of terminal output represent filenames, PIDs, web URLs or IP addresses and provides context-aware commands for each of them.
New semantic menus can be added effortlessly with a powerful yet simple text file-based plug-in system — no programming required.
Final Term knows when it is displaying a command prompt to you, and it knows all the commands that you ever entered.
The moment you start typing, suggestions from your terminal history automatically pop up — lightning fast and sorted by an algorithm that ensures what you want to type is almost always right at the top.
Final Term lets you collapse command output much like a programmer's editor lets you fold code.
Final Term recognizes "ASCII art scrollbars" in the output of supported programs like wget and displays matching GUI scrollbars, allowing you to monitor progress while the output is scrolled away.
In addition to these standouts, Final Term also contains the best of features found in traditional terminal emulators:
Binding any key (or combination of keys) to arbitrarily many functions is as simple as editing a text file. Have a look:
<Ctrl>L = RUN_SHELL_COMMAND "ls -lh"
This will cause Ctrl+L to execute the command ls -lh
in the shell. If you can decipher that, you have already mastered Final Term keybindings.
In addition to application-level keybindings, Final Term also allows you to define arbitrarily many global (i.e. system-wide) shortcuts. These use the same syntax as local ones, but make Final Term do your bidding regardless of which application has the focus.
Final Term supports 8 terminal colors.
Final Term supports 16 terminal colors.
Final Term supports 256 terminal colors out of the box.
And Final Term is one of the very few terminal emulators that support 24-bit RGB terminal colors.
All of these colors can be customized using color schemes, of which Final Term already ships 10 beautiful ones by default — each of them in a light and a dark version. More can easily be generated using the supplied Base16 Builder template.
This feature, as famously seen in the Mac OS terminal, has been among the most requested ones from Linux terminal programs for several years now.
Well, the wait is over. Final Term does it, no need for hacks (screen), no questions asked.
Final Term's beautiful, hardware-accelerated user interface redefines what you can expect from a terminal emulator's GUI. Everything is slick, smooth and animated.
Whether you are working on your day job or in the deepest night, Final Term will dress accordingly: With a single switch, the interface flips from light to dark and back.
If that alone does not fulfill your customization needs, do not worry — the entire UI can be skinned using themes.
Inspired by the wonderful Guake (and, ultimately, Quake), Final Term drops down from the top of your screen at the press of a key and slides up when the same key is pressed again.
Another key simply brings the terminal window to the foreground when it is hidden, and hides it again.
Exactly which keys do that? Your choice, of course...
Cover image: Autopilot (Wikimedia Commons, CC-BY-SA)
]]>Version 0.0.5, last modified 6-Ples-2012 (November 17th, 2012)
]]>Note:
This is not a calendar application, a calendar library, a calendar API, a calendar in "the cloud", a calendar template, or anything else directly related to computer technology for that matter.
This is a calendar, a system
Version 0.0.5, last modified 6-Ples-2012 (November 17th, 2012)
Note:
This is not a calendar application, a calendar library, a calendar API, a calendar in "the cloud", a calendar template, or anything else directly related to computer technology for that matter.
This is a calendar, a system that helps humans track time, like its Gregorian, Maya, Dreamspell and Minguo counterparts.
An implementation of cal-ender's date logic in JavaScript can be found in cal-ender's GitHub repository.
cal-ender is an alternative to the ubiquitous Gregorian calendar, designed from the ground up to complement rather than replace it. It is closely aligned with the Gregorian and works alongside it while mitigating many of the Gregorian calendar's shortcomings – enabling you to make the switch without having to wait for the rest of the world to do the same.
For the design of cal-ender's date arithmetic and alignment with the Gregorian calender, the following objectives were considered paramount, in order of importance (chosen by evaluating the presumed frequency of use of the operations involved):
A cal-ender date is given by a day, a month and a year. Every Gregorian date is assigned exactly one cal-ender date, and vice versa. The Gregorian weekday naming scheme is retained in cal-ender and the weekday of a cal-ender date is taken to be that of its corresponding date in the Gregorian calendar.
A cal-ender year consists of 13 months. The first 12 months always consist of precisely 28 days, or four weeks, each. The 13th month has either 28 or 35 days, bridging the years. cal-ender can thus be classified as a 13 month, leap week calendar.
Every cal-ender year starts with the first Monday in Gregorian March, i.e. the first day of the first month of a cal-ender year always falls on a Gregorian date between March 1st and March 7th. Every cal-ender year thus ends with a Sunday.
It follows that the weekday of a cal-ender date is independent of year and month. This makes cal-ender a doubly perennial calendar both in terms of years and months.
There is a one-to-one mapping between Gregorian and cal-ender years. The year number of a cal-ender year is taken to be the year number of the Gregorian year that contains the cal-ender year's first day.
Since the weekday in cal-ender is determined by the day number alone, the day number is the most important item in a cal-ender date. It is therefore written first, followed by the month name or number and the year number. No ordinal indicators are used for any part of the date, as these are highly language dependent.
Acceptable date formats in cal-ender include:
Weekdays for cal-ender dates are not normally specified explicitly, as they are trivially computable given the day number.
The months of each year are numbered 1-13 and named the following:
These names were generated using yould, a Markov chain-based model of pronouncability in several natural languages. Note: The yould website is offline as of 2012. yould can be downloaded here.
The following command was used to generate 20 pronouncable words of length LENGTH:
yould -m LENGTH -M LENGTH -n 20
The (subjectively) most fitting word was chosen from the resulting list, or the process repeated if no fitting word was found. The names of some months were slightly modified from yould's output.
There are several design points behind this naming scheme:
This section aims to not only list but actually derive the key properties of the cal-ender system. The use of some formalism and arithmetic is therefore unavoidable. In particular, it is assumed that the reader is familiar with
The variation in length of the 13th month (and thus the variation of the year length) can be determined as follows:
Since the Gregorian leap day is always at or very nearly at the end of the cal-ender year, the mapping between Gregorian and cal-ender dates for most days depends only on the date of the cal-ender new year, not on whether the underlying Gregorian year is a leap year or not.
The day $s(y)$ of the first Monday in March (1#1#y) of a year $y$ can be determined from two factors:
The values of $s(y)$ for all possible combinations of these two factors are captured in the following table:
$s(y-1)$ | Common year | Leap year |
---|---|---|
1 | 7 | 6 |
2 | 1 | 7 |
3 | 2 | 1 |
4 | 3 | 2 |
5 | 4 | 3 |
6 | 5 | 4 |
7 | 6 | 5 |
This table can be expressed in closed form as follows:
$$s(y) = 7 - (8 - s(y-1) + p(y)) \bmod 7$$
where $s(y)$ is the day in March on which 1#1#y falls and $p(y)$ is the leap year function
$$
p(y) =
\begin{cases}
1 & y\text{ is a leap year} \\
0 & \text{otherwise}
\end{cases}
$$
which in the Gregorian calendar is equivalent to
$$
p(y) =
\begin{cases}
1 & (y \bmod 4 = 0 \land y \bmod 100 \ne 0) \lor y \bmod 400 = 0 \\
0 & \text{otherwise}
\end{cases}
$$
Given that $s(1583) = 4$, $s(y)$ can be computed recursively for all years $y > 1583$ using these formulae (note that 1583 is the first full year for which the Gregorian calendar was used).
A leap year in cal-ender is one that has 371 days (or 53 weeks), as opposed to a common year of 364 days (52 weeks). From the above table it can be seen that this occurs in two cases:
Given knowledge of the Gregorian leap years (see the function $p(y)$ above), cal-ender leap years are thus easy to identify. As a rule of thumb, they occur roughly every 5 or 6 years.
The cal-ender year cycle is completely determined by the fluctuation of the date of the first Monday in March over the years. Since relative to the same day in the previous year, that date is determined by the length of the Gregorian year (either 365 or 366 days), and Gregorian year lengths are periodic with a period of 400 years (see the function $p(y)$ above), it follows that the cal-ender year cycle is also periodic with the same period of 400 years.
By design, the most common calendar operation is the easiest in cal-ender: The weekday of a cal-ender date d#m#y is just
$$d \bmod 7$$
where $0$ = Sunday, $1$ = Monday, $2$ = Tuesday, $3$ = Wednesday, $4$ = Thursday, $5$ = Friday, $6$ = Saturday. Note that the weekday is independent of month and year. This is because every year starts with a Monday and every month has an integer number of weeks.
Calculating how many days lie between two dates is another fairly common operation that for many practical cases is greatly simplified in cal-ender when compared to the Gregorian calendar, owing to cal-ender's uniform month structure.
The number of days between two dates d1#m1#y1 and d2#m2#y2 is
$$|d1-d2| + 28\, |m1-m2| + 364\, |y1-y2| + 7\, p$$
where $p$ is the number of cal-ender leap years between the dates. If both dates lie in the same year, this formula simplifies to
$$|d1-d2| + 28\, |m1-m2|$$
With some practice, this calculation can be performed mentally in mere seconds.
While the theory is straightforward, converstion between arbitrary cal-ender and Gregorian dates is a difficult task to accomplish mentally. To make it less daunting, two concepts are helpful:
The cal-ender day number $n$ of a date d#m#y which is defined as
$$n(d,m,y) = d + 28\, (m-1)$$
and is simply equivalent to the index of the day in the cal-ender year
The shifted cal-ender day number $n'$:
$$n'(d,m,y) = n(d,m,y) + s(y)$$
Because $s(y)$ is the number of days by which the start of the cal-ender year $y$ is shifted after the last day of February, the Gregorian date of a cal-ender date d#m#y with shifted day number $n'$ is independent of $y$ and can be looked up in the following table:
Gregorian date | $n'$ |
---|---|
March 1st | 2 |
April 1st | 33 |
May 1st | 63 |
June 1st | 94 |
July 1st | 124 |
August 1st | 155 |
September 1st | 186 |
October 1st | 216 |
November 1st | 247 |
December 1st | 277 |
January 1st (y+1) | 307 |
February 1st (y+1) | 338 |
Having memorized this table (which never changes) as well as $s(y)$ for the year in question (which has to be memorized only once anually if one is solely interested in the current year), one can convert from cal-ender to Gregorian dates and vice versa by interpolating appropriately. While this may take a while to master, it is very much within the reach of anybody possessing a basic grasp of arithmetic, and is certainly no more complex than commonly used methods for mental weekday computation in the Gregorian calendar.
Naturally, computers have no difficulty whatsoever performing this conversion, so if one is willing to rely on electronic help even these obstacles disappear entirely.
In the past centuries, the Gregorian calendar has superseded many other calendars around the world, a process that didn't always go smoothly. As a result, many cultures celebrate certain feasts on dates that are derived from an obsolete (often lunisolar) calendar which aligns poorly with the Gregorian, making computation of the date of these festivities in a specific year an important and challenging problem that is transferred to cal-ender.
Many Christian holidays (and, by consequence, some state holidays in predominantly Christian countries) are dependent on the date of Easter in terms of being celebrated a fixed number of days before or after Easter Sunday. The computation of the date of Easter Sunday is therefore of vital importance for many calendar applications.
Easter computation in the Gregorian calendar is notoriously complicated as highlighted by the fact that the period of the Gregorian Easter cycle is a dazzling 5.7 million years. While a large part of the complexity remains, Easter computation is simplified in cal-ender for two reasons:
The dates on which Easter Sunday can fall may be determined as follows:
cal-ender thus has only 6 possible Easter dates while the Gregorian calendar has 35. Numerical investigation additionally shows that 28#2 is very rare as an Easter date, occuring only 7 times per millenium on average. The full distribution of cal-ender Easter dates is as follows (sampled from the period 10,000 AD-110,000 AD):
Date | Frequency |
---|---|
21#1 | 10.0 % |
28#1 | 23.3 % |
7#2 | 23.3 % |
14#2 | 23.3 % |
21#2 | 19.2 % |
28#2 | 0.7 % |
TBD
TBD
TBD
TBD
The following is an informal, subjective comparison between cal-ender and the system it is designed to augment and replace.
Cover image: Abraham and Jehuda Cresques (Wikimedia Commons, Public domain)
]]>