October 2017 - mathfun@mailman.xmission.com

Re: [math-fun] prime targets for Coppersmith hacking
by Henry Baker 17 Oct '17

17 Oct '17

FYI -- More info... >Date: Mon, 16 Oct 2017 18:25:18 -0700 >From: John Gilmore <gnu(a)toad.com> > >The essence of the test for broken keys is a list of primes and a list of remainder masks. > >"git clone https://github.com/crocs-muni/roca" and examine roca/roca/detect.py: > >Here's the test: > >for i in range(0, len(self.primes)): > if (1 << (modulus % self.primes[i])) & self.prints[i] == 0: > return False >self.primes = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, > 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167] >self.prints = [6, 30, 126, 1026, 5658, 107286, 199410, 8388606, 536870910, 2147483646, 67109890, 2199023255550, > 8796093022206, 140737488355326, 5310023542746834, 576460752303423486, 1455791217086302986, > 147573952589676412926, 20052041432995567486, 6041388139249378920330, 207530445072488465666, > 9671406556917033397649406, > 618970019642690137449562110, > 79228162521181866724264247298, > 2535301200456458802993406410750, > 1760368345969468176824550810518, > 50079290986288516948354744811034, > 473022961816146413042658758988474, > 10384593717069655257060992658440190, > 144390480366845522447407333004847678774, > 2722258935367507707706996859454145691646, > 174224571863520493293247799005065324265470, > 696898287454081973172991196020261297061886, > 713623846352979940529142984724747568191373310, > 1800793591454480341970779146165214289059119882, > 126304807362733370595828809000324029340048915994, > 11692013098647223345629478661730264157247460343806, > 187072209578355573530071658587684226515959365500926] > >So you divide the RSA public key by this set of small primes, and examine the remainder. > >If the bit in the matching "prints" number that matches the remainder is on, the key is not vulnerable. > >If any of the remainders indexes a bit that's zero, the key is vulnerable. > >All the "prints" numbers are even, i.e. their low order bit is zero: > >if the remainder when dividing by any small prime is zero, then, ahem, the number is easy to factor! > >What does this tell us about how the keys were poorly generated, and what does it tell us about how to factor them? > >(We'll find out in early November, but we might as well think about it.)

2 2

[math-fun] Identities : formulas (13,15,16,...,25)
by François Mendzina Essomba 17 Oct '17

17 Oct '17

Hello, just to let ... product(cos(theta/5^k)-4*(sin(theta/(4*5^k)))^2*cos(theta/(2*5^k)), k, 1, inf)=cos(theta/4); prod((cos(theta/5^(k))+4*(cos(theta/(4*5^(k))))^2*cos(theta/(2*5^(k))))/5,k,1,inf)=(4/(theta))*sin(theta/4); product(cos(theta/5^(k/2))-4*(sin(theta/(4*5^(k/2))))^2*cos(theta/(2*5^(k/2))), k, 1, inf)=cos(theta/4)*cos(theta*sqrt(5)/4); product(cos(theta/5^(k/3))-4*(sin(theta/(4*5^(k/3))))^2*cos(theta/(2*5^(k/3))), k, 1, inf)=cos(theta/4)*cos(theta*5^(1/3)/4)*cos(theta*5^(2/3)/4); product(cos(theta/5^(k/7))-4*(sin(theta/(4*5^(k/7))))^2*cos(theta/(2*5^(k/7))), k, 1, inf)=cos(theta/4)*cos(theta*5^(1/7)/4)*cos(theta*5^(2/7)/4)*cos(theta*5^(3/7)/4)*cos(theta*5^(4/7)/4)*cos(theta*5^(5/7)/4)*cos(theta*5^(6/7)/4); product(cos(theta/5^(k/m))-4*(sin(theta/(4*5^(k/m))))^2*cos(theta/(2*5^(k/m))), k, 1, inf)=prod(cos(5^(i/m)*theta/4),i,0,m-1); prod((cos(theta/5^(k/m))+4*(cos(theta/(4*5^(k/m))))^2*cos(theta/(2*5^(k/m))))/5,k,1,inf)=(4^m/(theta)^m)*prod(sin(5^(i/m)*theta/4)/5^(i/m),i,0,m-1); Euler's identity extension: product(cos(theta/2^(n/m)),n,1,inf)=product(sin(2^(i/m)*theta)/2^(i/m),i,0,m-1)/theta^m; with hyperbolic functions: product(cosh(theta/2^n),n,1,inf)=sinh(theta)/theta; product(cosh(theta/2^(n/m)),n,1,inf)=product(sinh(2^(i/m)*theta)/2^(i/m),i,0,m-1)/theta^m; prod(2*cosh(theta/2^(n/m))-1,n,1,inf)=prod((1+2*cosh(2^(i/m)*theta))/3,i,0,m-1); prod((2*cosh(theta/3^(n/m))+1)/3,n,1,inf)=(2^m/(theta)^m)*prod(sinh(3^(i/m)*theta/2)/3^(i/m),i,0,m-1); prod((cosh(theta/5^(k/m))+4*(cosh(theta/(4*5^(k/m))))^2*cosh(theta/(2*5^(k/m))))/5,k,1,inf)=(4^m/(theta)^m)*prod(sinh(5^(i/m)*theta/4)/5^(i/m),i,0,m-1); Best regards

1 0

[math-fun] Estonian citizens prime targets for Coppersmith hacking
by Henry Baker 16 Oct '17

16 Oct '17

FYI -- Once again, *security by obscurity* doesn't work for 58% of the Estonian population -- in this case the inaptly-named "Trusted Platform Modules" can't generate hard-to-factor RSA numbers. So much for Estonian voting and democracy. https://arstechnica.com/information-technology/2017/10/crypto-failure-cripp… COMPLETELY BROKEN -- Millions of high-security crypto keys crippled by newly discovered flaw Factorization weakness lets attackers impersonate key holders and decrypt their data. Dan Goodin - Oct 16, 2017 11:00 am UTC A crippling flaw in a widely used code library has fatally undermined the security of millions of encryption keys used in some of the highest-stakes settings, including national identity cards, software- and application-signing, and trusted platform modules protecting government and corporate computers. The weakness allows attackers to calculate the private portion of any vulnerable key using nothing more than the corresponding public portion. Hackers can then use the private key to impersonate key owners, decrypt sensitive data, sneak malicious code into digitally signed software, and bypass protections that prevent accessing or tampering with stolen PCs. The five-year-old flaw is also troubling because it's located in code that complies with two internationally recognized security certification standards that are binding on many governments, contractors, and companies around the world. The code library was developed by German chipmaker Infineon and has been generating weak keys since 2012 at the latest. The flaw is the one Estonia's government obliquely referred to last month when it warned that 750,000 digital IDs issued since 2014 were vulnerable to attack. Estonian officials said they were closing the ID card public key database to prevent abuse. On Monday, officials posted this update. Last week, Microsoft, Google, and Infineon all warned how the weakness can impair the protections built into TPM products that ironically enough are designed to give an additional measure of security to high-targeted individuals and organizations. Completely broken "In public key cryptography, a fundamental property is that public keys really are public--you can give them to anyone without any impact in security," Graham Steel, CEO of encryption consultancy Cryptosense, told Ars. "In this work, that property is completely broken." He continued: It means that if you have a document digitally signed with someone's private key, you can't prove it was really them who signed it. Or if you sent sensitive data encrypted under someone's public key, you can't be sure that only they can read it. You could now go to court and deny that it was you that signed something--there would be no way to prove it, because theoretically, anyone could have worked out your private key. Both Steel and Petr Svenda, one of the researchers who discovered the faulty library, also warned the flaw has, or at least had, the potential to create problems for elections in countries where vulnerable cards are used. While actual voter fraud would be difficult to carry out, particularly on a scale needed to sway elections, "just the possibility (although impractical) is troubling as it is support for various fake news or conspiracy theories," Svenda, who is a professor at Masaryk University in the Czech Republic, told Ars. Invoking the prolific leakers of classified National Security Agency material, Steel added: "Imagine a Shadowbrokers-like organization posts just a couple of private keys on the Internet and claims to have used the technique to break many more." The flaw is the subject of a research paper titled The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli, which will be presented on November 2 at the ACM Conference on Computer and Communications Security. The vulnerability was discovered by Slovak and Czech researchers from Masaryk University in the Czech Republic, Enigma Bridge in Cambridge, UK, and Ca' Foscari University in Italy. To give people time to change keys, the paper describing the factorization method isn't being published until it's presented at the conference. https://en.wikipedia.org/wiki/Coppersmith%27s_Attack The flaw resides in the Infineon-developed RSA Library version v1.02.013, specifically within an algorithm it implements for RSA primes generation. The library allows people to generate keys with smartcards rather than with general-purpose computers, which are easier to infect with malware and hence aren't suitable for high-security uses. The library runs on hardware Infineon sells to a wide range of manufacturers using Infineon smartcard chips and TPMs. The manufacturers, in turn, sell the wares to other device makers or end users. The flaw affects only RSA encryption keys, and then only when they were generated on a smartcard or other embedded device that uses the Infineon library. To boost performance, the Infineon library constructs the keys' underlying prime numbers in a way that makes them prone to a process known as factorization, which exposes the secret numbers underpinning their security. When generated properly, an RSA key with 2048 bits should require several quadrillion years--or hundreds of thousands of times the age of the universe--to be factorized with a general-purpose computer. Factorizing a 2048-bit RSA key generated with the faulty Infineon library, by contrast, takes a maximum of 100 years, and on average only half that. Keys with 1024 bits take a maximum of only three months. The factorization can be dramatically accelerated by spreading the load onto multiple computers. While costs and times vary for each vulnerable key, the worst case for a 2048-bit one would require no more than 17 days and $40,300 using a 1,000-instance machine on Amazon Web Service and $76 and 45 minutes to factorize an affected 1024-bit key. On average, it would require half the cost and time to factorize the affected keys. All that's required is passing the public key through an extension of what's known as Coppersmith's Attack. While all keys generated with the library are much weaker than they should be, it's not currently practical to factorize all of them. For example, 3072-bit and 4096-bit keys aren't practically factorable. But oddly enough, the theoretically stronger, longer 4096-bit key is much weaker than the 3072-bit key and may fall within the reach of a practical (although costly) factorization if the researchers' method improves. To spare time and cost, attackers can first test a public key to see if it's vulnerable to the attack. The test is inexpensive, requires less than 1 millisecond, and its creators believe it produces practically zero false positives and zero false negatives. The fingerprinting allows attackers to expend effort only on keys that are practically factorizable. The researchers have already used the method successfully to identify weak keys, and they have provided a tool here to test if a given key was generated using the faulty library. A blog post with more details is here. https://keychest.net/roca https://roca.crocs.fi.muni.cz/ In search of vulnerable keys The researchers examined keys used in electronic identity cards issued by four countries and quickly found two--Estonia and Slovakia--were issuing documents with fingerprinted keys, both of which were 2048 bits in length, making them practically factorizable. Estonia has disclosed the flaw in what it said were 750,000 of the cards issued since 2014. Ars checked the key used in an e-residency card Ars Senior Business Editor Cyrus Farivar obtained in 2015, and it came back as factorizable. While it has closed its public key database, Estonian government officials have also announced plans to rotate all keys to a format that's not vulnerable, starting in November. The status of Slovakia's system isn't immediately clear. With two of the four countries checked testing positive for fingerprinted keys, a more exhaustive search is likely to identify many more nations issuing cards with factorizable keys. Next, the researchers examined a sampling of 41 different laptop models that used trusted platform modules. They found vulnerable TPMs from Infineon in 10 of them. The vulnerability is especially acute for TPM version 1.2, because the keys it uses to control Microsoft's BitLocker hard-disk encryption are factorizable. That means anyone who steals or finds an affected computer could bypass the encryption protecting the hard drive and boot sequence. TPM version 2.0 doesn't use factorizable keys for BitLocker, although RSA keys generated for other purposes remain affected. Infineon has issued a firmware update that patches the library vulnerability, and downstream affected TPM manufacturers are in the process of releasing one as well. The researchers also scanned the Internet for fingerprinted keys and quickly found hits in a variety of surprising places. They found 447 fingerprinted keys--237 of them factorizable--used to sign GitHub submissions, some for very popular software packages. GitHub has since been notified of the fingerprinted keys and is in the process of getting users to change them. The researchers also found 2,892 PGP keys used for encrypted e-mail, 956 of which were factorizable. The researchers speculated that the majority of the PGP keys were generated using the Yubikey 4, which allows owners to use the faulty library to create on-chip RSA keys. Other functions of the USB device, including U2F authentication, remain unaffected. Yubico has more details here. https://www.yubico.com/keycheck/ The researchers went on to find 15 factorizable keys used for TLS. Strangely, almost all of them contain the string "SCADA" in the common name field. That raised the possibility the certificates are being used by an organization involved in Supervisory Control And Data Acquisition, which uses computers to control dams, electric substations, and other industrial equipment. All 15 fingerprinted keys have a characteristic involving their prime numbers that is outside the range of what's produced by the faulty Infineon library, raising the possibility there was a modification of it that hasn't yet been documented. This is the second time in four years that a major crypto flaw has been found hitting a crypto scheme that has passed rigorous certification tests. In 2013, a different set of researchers unearthed flaws in Taiwan's secure digital ID system that would allow attackers to impersonate some citizens. Both the flawed Infineon library and the Taiwanese digital ID system passed the FIPS 140-2 Level 2 and the Common Criteria standards. Both certifications are managed by the National Institute of Standards and Technology. Both certifications are often mandatory for certain uses inside government agencies, contractors, and others. The researchers who uncovered the Infineon library flaw questioned whether the secrecy required by some of the certification process played a role. They wrote: Our work highlights the dangers of keeping the design secret and the implementation closed-source, even if both are thoroughly analyzed and certified by experts. The lack of public information causes a delay in the discovery of flaws (and hinders the process of checking for them), thereby increasing the number of already deployed and affected devices at the time of detection. All told, the researchers estimate that Infineon's faulty library may have generated tens of millions of RSA keys in the five or so years it has been commercially available. A good many of them are practically factorizable, but even those that are not are considerably more vulnerable to factorization than federal standards and common-sense security guidelines dictate. RSA keys generated with OpenSSL, PGP-compliant programs, or similar computer programs aren't affected. People who have relied on smartcards or embedded devices for cryptographic functions should test their RSA keys using the researchers' fingerprinting tool. In the event the keys test positive, people should revoke them as soon as possible and generate new ones. Keys using Elliptic Curve Cryptography and other non-RSA methods aren't affected. It's going to take a while for people to identify all vulnerable keys. They should start by replacing those that are known to be practically factorizable, but eventually all RSA keys generated by the flawed library should go. Cryptographers and engineers within NIST and other standards organizations should also use the failure to learn how to improve their high-security certifications processes. Promoted Comments vintagedave Wise, Aged Ars Veteran Quote: Estonia has disclosed the flaw in what it said were 750,000 of the cards issued since 2014. Ars checked the key used in an e-residency card Ars Senior Business Editor Cyrus Farivar obtained in 2015 and it came back as factorizable. I live in Estonia. A couple of interesting or concerning points here: * The population is 1.3 million. 750,000 affected cards sounds plausible for the majority or even entire adult population. No material that I've seen in articles (here) or online (eg Estonian government) have mentioned a breakdown of the affected cards by population, voting rights, or residency. Ars - a good opportunity for some investigative journalism? * Estonia is a nation at risk from Russian cyber attacks. It's happened before. Here's CEPA's analysis of the current situation as of 2016. * We had municipal elections yesterday, and online voting using ID cards is common. Municipal elections are important in this country: consider the ex-mayor of Tallinn Edgar Savisaar and the social turmoil and potential Russian-related corruption attributed to him. Dan Goodin Dan is the Security Editor at Ars Technica, which he joined in 2012 after working for The Register, the Associated Press, Bloomberg News, and other publications. Email dan.goodin(a)arstechnica.com // Twitter @dangoodin001

1 0

Re: [math-fun] Random slice of a cube
by Keith F. Lynch 16 Oct '17

16 Oct '17

Bill Gosper <billgosper(a)gmail.com> > Keith F. Lynch wrote: >> I am not a visual thinker. I'm not even sure what numbers of sides >> the polygon could have. It can obviously have 3, 4, or 6. I doubt >> it can have more than 6, but I'm not sure. I'm even less sure >> whether it can have 5. > gosper.org/pentagonal cubeslice.png Thanks. I also see now that it can never have more than six, since each side is formed by the plane's intersection with a face of the cube, and cubes only have six faces, all of which are convex. I'm curious what the maximum numbers of sides are for the polygons formed by the intersection of a plane with the other regular polygons. I can obviously get all four with the tetrahedron, but I'm not at all sure what the number is for the other three regular solids. I'm guessing it's ten for the dodecahedron. I'm pretty sure it's not possible to get a polygon with fewer than four sides from a plane's intersection with an octahedron, or with fewer than five sides from a plane's intersection with an icosahedron. Since nobody else seems to have done so, I wrote a quick program to generate (pseudo-)random planes and count sides (for the cube only, not for other regular polygons). The program is not visual, so I'm largely taking it on faith that it's doing what I told it to do, but it did pass several sanity checks. For instance: * It only finds polygons with 3, 4, 5, or 6 sides. * If I set Max_D (the maximum distance from the center of the cube to the intersection with the plane) to 0, I only get 4 or 6 sides. * If I increase Max_D the proportions gradually change, and if I increase Max_D beyond the square root of 3 the proportions cease changing. The average number of sides is 4.0004. The proportion of each number of sides: 3: 27.97 % 4: 48.68 % 5: 18.70 % 6: 4.65 % The last digit should not be trusted, but the other digits should be good. Could the average be exactly 4? It's a couple sigmas out, but it's possible. The proportions for planes that pass through the center of the cube are 64.9% four sides and 35.1% six sides. Ideally, someone else will write their own program, and see if it gets similar numbers. Unfortunately, my program cannot easily be adapted to other regular polygons. For all three ways of choosing two of X, Y, and Z, I set those two to the four combinations of -1 and +1, then solve for the third. If the third is between -1 and +1, I've found an intersection between the plane and an edge of the cube. This would have to be completely rewritten for other regular solids. I could easily collect statistics on the side lengths and angles of the intersecting polygons, if anyone is interested.

3 2

Re: [math-fun] Random slice of a cube
by James Propp 16 Oct '17

16 Oct '17

I should've written "regular tetrahedra". Jim On Monday, October 16, 2017, Warren D Smith <warren.wds(a)gmail.com> wrote: > On 10/16/17, James Propp <jamespropp(a)gmail.com <javascript:;>> wrote: > > More specifically, it doesn't bode well for a nice answer for the > > tetrahedron. Tetrahedra don't tile space, so Warren's type of argument > does > > not seem to be available. > > Actually, you are wrong: > Regular tets do not tile, but there exist nonregular tets that do tile > (and in a lovely-face-to-face manner). > The nicest of them is the "BCC tetrahedron" which arises in the > Delaunay triangulation of the BCC point-lattice. >

1 0

Re: [math-fun] Random slice of a cube
by James Propp 16 Oct '17

16 Oct '17

I googled for five minutes and looked at half a dozen articles; I saw various models of random polytopes, but none of them appeared to be of the form "choose a random plane that intersects a polytope nontrivially and then take that intersection". I also didn't find the resilt about random polygons that Warren mentioned (the one that says that a random polygon has 4 sides on average). So if Warren or anyone else can provide more leads, I'd appreciate it! Jim Propp On Sunday, October 15, 2017, Warren D Smith <warren.wds(a)gmail.com> wrote: > I believe there is a known published model of "random polytopes" > in which the exact expected value is 4. >

2 4

[math-fun] Gosper's identities
by François Mendzina Essomba 16 Oct '17

16 Oct '17

Hello, I found in the page http://www.tweedledum.com/rwg/idents.htm strange identities, as incredible as each other ... I have observed at length some of the identities ranging from C105 to C115. And this is what I deduced from it: (9) D106 product(2*cos(theta/3^(n/m))-1,n=1..infinity)=product(cos(3^(i/m)*theta/2),i=0...m-1) ; (10) D105 product(2*cos(theta/2^(n/m))-1,n=1..infinity)=product((1+2*cos(2^(i/m)*theta))/3,i=0..m-1); (11) D110 product((2*cos(theta/3^(n/m))+1)/3,n=1..infinity)=(2^m/(theta)^m)*product(sin(3^(i/m)*theta/2)/3^(i/m),i=0..m-1); However I am a little perplexed as to the last formula that differs from Gosper's D111 identity by a factor of 4. The result I get is this: (12) D111 product((2*cos(theta/3^(n/2))+1)/3,n=1..infinity)=(2^2/(theta)^2)*product(sin(3^(i/2)*theta/2)/3^(i/2),i=0..2-1); I suppose it must be the same for this small series, I have yet to check. Best regards

1 0

Re: [math-fun] Random slice of a cube
by Dan Asimov 15 Oct '17

15 Oct '17

Keith Lynch wrote: ----- ... I would ask, not what the average number of sides is, but the proportion of each number of sides ... ----- And then for each number of sides, its proportion is averaged over all planes (obtained by the 3-points-on-circumsphere method)? Or if not, what? —Dan

3 3

[math-fun] Da Vinci "orb" & optics
by Henry Baker 15 Oct '17

15 Oct '17

You're going to be hearing a lot about the recently "authenticated" painting by Leonardo da Vinci called "Salvator Mundi", because it will be auctioned at Christie's in November 2017 for hundreds of millions of dollars. https://en.wikipedia.org/wiki/Salvator_Mundi_(Leonardo_da_Vinci) The Wikipedia link to a jpeg of the picture itself: https://upload.wikimedia.org/wikipedia/commons/1/1f/Leonardo_da_Vinci_or_Bo… Here's a major problem IMHO with this painting: The (supposedly rock crystal) "orb" should distort the image behind it far more than it does in this painting, and da Vinci *would have known this*, as he did a lot of experiments with lenses and mirrors, designed lens and mirror grinding apparati, knew about the camera obscura, and supposedly invented the first *contact lens*! (I myself own a solid glass sphere much like the one in the painting, and I can vouch for the substantial distortion it makes when you view objects through it.) Da Vinci was famous for constantly updating his paintings (many of which were never finished) when he learned something new that would change how the painting should look. E.g., Isaacson's new biography of da Vinci mentions the fact that da Vinci updated the neck area of a painting after his human dissections showed that the neck muscle was different from what he had previously assumed. There are several possible explanations for the lack of orb distortion in the painting being auctioned by Christie's: * the particular area of the painting has undergone *bad conservation* by conservators who demonstrated their profound ignorance of optics when "repairing" the painting; * the orb isn't a sphere at all, but a thinner *lens*; but why in the world would da Vinci replace the standard spherical orb symbol with a lens? Possibly as an inside joke re his use of lenses to get his images right (see artist David Hockney's theories about these Renaissance painters and their optical devices)? https://en.wikipedia.org/wiki/Hockney%E2%80%93Falco_thesis * the orb isn't solid at all, but more like a transparent glass Christmas tree ornament, so it wouldn't distort the image underneath nearly as much as a solid rock crystal. Glass blowers could have made such a hollow orb for da Vinci, and da Vinci was known to have experimented with hollow glass "lenses" which he filled with water & other liquids for experimentation. Isaacson and the "experts" at Christie's claim that da Vinci went to a lot of trouble to paint "inclusions" (small bubbles) in the supposedly rock crystal material. They even claim that the crystal could be doubly refracting, and that da Vinci captured that. Then why in the world would da Vinci screw up the even more obvious feature -- the distortion caused by this supposedly solid crystal object? Perhaps there is a simpler explanation: the little dots aren't *inclusions* at all, but *specular reflections* of da Vinci's lights used to illuminate the orb model while it was being painted? Specular highlights would also be consistent with a hollow glass sphere or a lens. BTW, the modern computer graphics technique of "ray tracing", which is the computer implementation of "geometric optics", is required to properly handle refractive objects -- e.g., lenses, orbs. Ray tracing is quite computationally intensive, requiring large supercomputers to implement; most of the latest Hollywood animated features incorporate the sophisticated effects obtained from ray tracing, although they don't want to go so far as to make the animations look "too good", else people will forget that they *are* animations. Some of the later Dutch painters loved to show off their incredible skill by including such distorted images from reflections in curved objects and through lenses. There was a Scientific American article from 30+ years ago that discussed some of these effects. https://en.wikipedia.org/wiki/Ray_tracing_(graphics) https://en.wikipedia.org/wiki/Geometrical_optics If one has a good enough model of the image behind such an orb, it should be possible to *invert* the ray tracing computation to reveal the actual shape of the lens/orb which is providing the distortion.

1 0

[math-fun] Looking for a recurrence related to Stern's diatomic array
by Neil Sloane 14 Oct '17

14 Oct '17

Stern's diatomic array (A049456) is a triangle in which row n lists the denominators in the n-th row of the table of Farey fractions. Another version of A049456 is the Stern-Brocot sequence (A002487) which has the recurrence a(2n)=a(n), a(2n+1)=a(n)+a(n+1), with a(0)=0, a(1)=1. There are a huge number of references. Someone recently asked me about a sequence which I was able to show was equal to the number of distinct terms in the n-th row of Stern's A049456. Surprisingly, this was not in the OEIS, although it is now - see A293160: 1, 2, 3, 5, 7, 13, 20, 31, 48, 78, 118, 191, 300, 465, 734, 1175, 1850, 2926, 4597, 7296, 11552, 18278, 28863, 45832, 72356, 114742, ... Can someone find a recurrence? (The smallest positive missing number from row n is A135510, which has an 1850 reference to Eisenstein.)

2 3