- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] A faster algorithm for π(x)
by Varun Rajkumar 14 Oct '19

14 Oct '19

Earlier, I had the doc π(n) and the Sieve of Eratosthenes <https://docs.google.com/document/d/1yzj1QZZzmqVG4ow6ScTR5bX5mDOKxNVkQGX7G-H…>, but I have a better algorithm: This is the same method as in the doc (read the doc and edit it) but we don't add 1 because then it will be hard to compute. What do you think of it? It works, I tried it. -Varun

2 1

[math-fun] A Permutation Cipher Text
by Brad Klee 12 Oct '19

12 Oct '19

https://0x0.st/zwRU.txt Easy to brute force if you get the gist of the permutation scheme but looks difficult to reverse engineer otherwise. Codebreaking algorithms? --Brad

3 4

Re: [math-fun] A Permutation Cipher Text
by Keith F. Lynch 12 Oct '19

12 Oct '19

Mike Stay <metaweta(a)gmail.com> wrote: > Keith F. Lynch <kfl(a)keithlynch.net> wrote: >> Some years ago it occurred to me that exclusive-oring a text with >> a subset of the square roots, in binary, of the first N primes, >> followed by the above scrambling algorithm (in ASCII order), >> followed by the same exclusive-oring again, would be a pretty >> good encryption algorithm. Does anyone disagree? > The scrambling is irrelevant if the ciphertext has length N and > the square roots of those N primes are GF(2)-linearly independent. I'm assuming that the square roots of the primes, expressed in binary, are all normal ("patternless") and uncorrelated with each other (i.e. the exclusive-or of any subset of them is also normal), though as far as I know neither has actually been proven. (I'm speaking of the digits after the radix point only.) > Just apply Gaussian elimination and you've reduced the cipher to a > one-time pad. > If N is less than the length of the ciphertext, then there will > likely be exploitable statistical correlations. N *is* less. It's just large enough that it's impractical to try all 2^N possible subsets of the first N primes, and will remain so for the foreseeable future. The main reason for the scrambling step is because I use the *same* subset of the primes for multiple files. (Well, almost the same. I append the low 24 bits of the file creation time (Unix time, seconds since 1970 began) to the subset.) Specifically, I hash, scramble, hash again, reverse-scramble, then hash again. This has the advantage that encryption and decryption are identical. Also, since it's an odd number of hashes (with the same subset), the number of 1-bits is not preserved, as it would be with an even number of hashes regardless of scrambling. "Hash" means exclusive-or the k-bit text with the first k bits of a subset of the first n primes exclusive-ored together. "Scramble" means reverse the text between each pair of identical characters, wrapping around so that the first and last characters aren't unmoved. I do this once for every character, in ASCII order. "Reverse scramble" is the same as scramble, but in reverse ASCII order. If what I'm proposing is sound, then scrambling would also allow for re-use of one time pads on multiple files.

2 1

[math-fun] Efficient way to find solutions?
by Mike Stay 12 Oct '19

12 Oct '19

I'd like to efficiently find solutions to constraints of the form lower1 <= ((x * 0x000001) mod 2^24) < upper1 && lower2 <= ((x * 0x088405) mod 2^24) < upper2 && lower3 <= ((x * 0x652819) mod 2^24) < upper3 && ... where the constants are consecutive powers of 0x088405. Brute-forcing the space isn't much work to do for a single set of upper and lower bounds, but when I've got 2^40 such sets, it's daunting. Any ideas? -- Mike Stay - metaweta(a)gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com

4 6

[math-fun] Unitary Transforms of Elliptic Curves?
by bradklee＠gmail.com 11 Oct '19

11 Oct '19

The proof that canonical or symplectic transformations leave invariant the real period of an elliptic curve is not too difficult using Jacobian matrices of determinant 1. Generalization of the proof seems to imply the corollary that complex determinant transformations from unitary act as rotation of the period parallelogram through the complex plane. It would be nice to have an intelligible reference on the full theorem, if it is correct. A few years ago I skimmed through every “Yellow Peril” textbook I could find on the subject (including Silverman), and didn’t find the answers I was looking for. Did I miss something, or am I just worried about another fact that is “obviously” right (or wrong)? — Brad

1 0

[math-fun] heptagonal stopsign nerdsnare
by Bill Gosper 11 Oct '19

11 Oct '19

Remember that XKCD where they blindside a passing nerd with a paralyzing math puzzle? add what for the next one? <http://gosper.org/hepstop7.bmp> What is the scale ratio of consecutive stopsigns? And consecutive "trumpets"? The guy behind you is honking his! —rwg

2 3

[math-fun] a(n), a(n+1) and a(n+2) don't share any digit
by Éric Angelini 10 Oct '19

10 Oct '19

Hello Math-Fun, How many terms in the hereunder finite seq? « a(n), a(n+1) and a(n+2) don't share any digit, with a(1) = 0. » Best, É.

5 5

[math-fun] Dragon functional equations
by Bill Gosper 10 Oct '19

10 Oct '19

A couple of weeks ago, Julian found Drag[(m + 1/2 + 1/4*(-1)^m)/2^n] == 1/2 (Drag[m/2^n] + Drag[(m + 1)/2^n]), for positive integers m, n, where Drag(t) is the usual Dragon-filling map of [0,1] into the bounding box [-1/3 - i/3, 7/6 + 2i/3]. This describes where along the Dragon is the *m*th vertex of the (self-avoiding) *n*th order "median curve". Using Julian's remarkable piecewiserecursivefractal interpolator-inverter applied to the Dragon's skin, as defined by http://larryriddle.agnesscott.org/ifs/heighway/heighwayBoundary.htm, I just noticed Out[161]= ConditionalExpression[dragskin[1/3 - t] ==3/2 + I/2 - dragskin[1/3 + t], Abs[t] <= 1/6] In[125]:= ConditionalExpression[I dragskin[1 - 3 t] == dragskin@t, 0 <= t <= 1/12] In[126]:= ConditionalExpression[I ( dragskin[1/2 - t] - 1) -> dragskin[1/2 + t] - 1, Abs@t <= 1/4] Plus an intriguing symmetry I haven't yet quantified, smooth scaling? <http://gosper.org/skin 012o3.png> The whole boundary is dragskin([0,1]). Unfortunately, Riddle's (really Mandelbrot's?) clever construction draws the skin at an unboundedly nonuniform rate. I.e., it has dimension D (an unlovely cubic surd between 1 (length) and 2 (area)), but its fill rate, measure(dragskin(t),t1<t<t2)/(t2-t1)^D, gets arbitrarily small. (And arbitrarily large?) But these functional relations raise my hope of finding some continuous, monotone u(t) to give dragskin(u) a uniform fill rate. —rwg Mandelbrot once challenged me to find the skin dimension. I disbelieved the irreducible cubic from a 5⨉5 determinant. Mandelbrot wrote only terse expressions. So I found a 6⨉6. Same damn cubic. I called him up. "Yes, that's the cubic." "How the heck did you get that? it's not your style!" "I just looked at how the wiggles fit into each other." It just occurs to me that I must have had two different, uniformly filling skin descriptions to write those determinants! Oh, to be young again.

3 3

Re: [math-fun] A Permutation Cipher Text
by Keith F. Lynch 09 Oct '19

09 Oct '19

Brad Klee <bradklee(a)gmail.com> wrote: > https://0x0.st/zwRU.txt > Easy to brute force if you get the gist of the permutation > scheme but looks difficult to reverse engineer otherwise. That looks very familiar. I notice that common letters remain common, that common digrams either remain common or are reversed, and that words and reversed words sometimes appear. I've seen that before, when I played around with taking a block of text and using each successive possible ASCII character in turn as a delimeter and reversing the text between every instance of that character, treating the end as being followed by the beginning (a "necklace"). For instance: reverse [e] revesre [r] rsevere [s] esrerev [v] erersev But I tried that, and it didn't work. Nor did running through the ASCII sequence in reverse order. Maybe another one of the 128! possible orders for seven-bit ASCII. It doesn't help that there are two non-ASCII characters in the text. Some years ago it occurred to me that exclusive-oring a text with a subset of the square roots, in binary, of the first N primes, followed by the above scrambling algorithm (in ASCII order), followed by the same exclusive-oring again, would be a pretty good encryption algorithm. Does anyone disagree?

2 1

[math-fun] The Triangle
by ed pegg 09 Oct '19

09 Oct '19

Some guy has been busy. https://arxiv.org/abs/1910.03379 --Ed Pegg Jr

2 1