Share this page!

Clément Canonne Profile picture
Twitter logo
4 Dec, 10 tweets, 6 min read
📊 Answers and discussion for yesterday's quiz on sequences (and their names).

Before we go to the first question, again: if you haven't, bookmark oeis.org. It's useful: the solution to some of your problems may be recorded there!

1/
So, the first question... was a trap. All three answers were valid...

I was personally thinking of 203, since that corresponds to the next Bell number (en.wikipedia.org/wiki/Bell_numb…).

But maybe your were thinking of something else? Maybe the number of...

2/
... ascent sequences avoiding the pattern 201 (oeis.org/A202062)? Or the number of set partitions of [n] that avoid 3-crossings (oeis.org/A108304)? Who am I to judge?

(I prefer Bell numbers.)

3/
Anyways, weird numbers are real! There even are infinitely many of them. en.wikipedia.org/wiki/Weird_num…

Superperfection exists, too. en.wikipedia.org/wiki/Superperf…

But I made up the Incredibles. It's a fiction. (54.3% of you correctly called me on this).

4/
Now, onto prime numbers... turns out, there are many, many types of them. But for quite a few of those classes, while people conjecture there exist an infinity of that type... people have no clue, really.

Except, e.g., Ramanujan primes, as 32.4% said.
5/
Mersenne primes? Not sure. Sophie Germain primes? Maybe. Wieferich primes? Bless you.

But Ramanujan primes, we even have their asymptotics.
en.wikipedia.org/wiki/Ramanujan…
6/
(The above is a figure from en.wikipedia.org/wiki/List_of_i…, by the way)

Speaking of asymptotics... let's look at Q4, and see who who goes the fastest?

That'd be the Bell numbers, as 47.5% answered. The prime numbers are very slow...

7/
... with the n-th satisfying p(n)~n log n (that's the Prime Number Theorem).

Catalan numbers go very fast, with log C(n)~n log 4.
But Bell numbers... wow. log B(n)~n log n.

(Note that I took the logarithm in the last two, as otherwise the asymptotics are quite annoying)

8/
To conclude, Q6. I made one up again, and nearly half of you got me. No "broke numbers."

Numbers can be polite, they can be fortunate, but somehow they can't be broke?

Well, if you ask me, that's unfortunate.

9/
Anyways, to conclude: integers are fun. Their names can be really bizarre, too: go and have a look!
en.wikipedia.org/wiki/List_of_i…
(and the OEIS, of course, is quite amusing to navigate at random)

That's all for today. If you have any comment, please don't hesitate!

10/end

• • •

Missing some Tweet in this thread? You can try to force a refresh
　

Keep Current with Clément Canonne

Clément Canonne Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @ccanonne_

Clément Canonne Profile picture
3 Dec
A paper with a broken and ill-defined "solution" to privacy in ML gets a $50k prize?! While said solution was already fully broken at the time of the award—on a challenge chosen by the authors?🤦‍♂️

The presentation slides must have been hella convincing.
Will Carlini et al. get a share of the prize money for breaking the system prior to the award ceremony? arxiv.org/abs/2011.05315
Disclaimer: I am in no way affiliated w/ any of the authors of the attack, nor w/ the authors of the original paper, nor w/ basically anyone involved. I'm just dismayed at the signal sent, & the overall waste—so much good work done elsewhere, and this is what gets the highlight.
Read 5 tweets
Clément Canonne Profile picture
3 Dec
📊 It's Thursday, time for our weekly (but weakly so) quiz! This week: integers, and remarkable sequences.

See this as an extended ad for the OEIS, if you will. Also, if you don't know the OEIS: go check it out (and come back)! oeis.org

1/
Let's start with a "fun" one. To be unhelpful, let's say as a hint that I'm expanding exp(e^x-1) as a series around 0, and am interested in the coefficients

Q1: Guess what number comes next—maybe this sequence will ring a bell? [There might be a trap]
1, 1, 2, 5, 15, 52, ??

2/
We won't do too many of those "guess what's next" games though, since they are mostly meaningless. But let's mention that, of course, @xkcdComic has a comic about integer sequences, because XKCD is basically Borges' library for the Internet.
xkcd.com/2016/
3/
Read 8 tweets
Clément Canonne Profile picture
27 Aug
📊 It's Thursday for many, time for this week's quiz! As alluded earlier, we're going to flip coins. Like, a lot.

Today: you have a biased coin which lands heads with some probability p∊(0,1), and you can toss it as many times as you want. You don't know p, though...

1/10
... which is a real shame, since you want to simulate *another* biased coin which lands heads w/ proba exactly f(p), where f: (0,1)→(0,1) is fixed.
(Also, you'd like to do this efficiently, thank you very much.)

Let's start with a simple function: f(p)=1/2.

Q1: Can you?

2/10
OK, so that was the warmup. Let's formalize a bit more what "efficiently" means here. For us, it will mean (1) with a number of coins finite almost surely (no infinite sequence of tosses), and (2) with a finite automaton.

Ha.

A finite automaton.

3/10
Read 10 tweets
Clément Canonne Profile picture
6 Aug
📊 It's Thursday [reference needed], time for a weᵄekly quiz! Given some recent events about randomized polynomial time (RP), it feels like a short discussion about 🎲 is topical.

So, let's go: Las Vegas, Monte Carlo, and... Bellagio (?) algorithms!

1/8
Let's start with some definitions—because that's fun, right. We'll discuss 3 types of decision algorithms: BPP (Monte Carlo), ZPP (Las Vegas), and RP (the... other) algorithms.

All three are randomized 🎲. What's the difference? The type of errors they allow.

2/8
↬BPP: efficient (run in poly time), can make mistakes but only w/ probability ≤¼

↬RP: efficient, can make mistakes but only when they say "no", and even then w/ probability ≤½

↬ZPP: efficient *in expectation* (yet could run forever sometimes), but never make mistakes.

3/8
Read 9 tweets
Clément Canonne Profile picture
30 Jul
📊 Today, (weakly|weekly) quiz will be about graphs. The ones with nodes and edges, not those plotting against you.

Specifically, *planar* graphs. The nice ones.

1/7
What's an (undirected) graph here? Just a pair G=(V,E) of n=|V| vertices (nodes) and m=|E| edges, where E ⊆ V×V and each edge in E is a pair (v₁,v₂) indicating if the two nodes v₁ and v₂ are connected.
If E=V×V (all possible edges), G is the complete graph, Kₙ.

2/7
(above, that's K₇, also very cool on t-shirts.). A graph G is *planar* if you can draw it on a sheet of paper w/o crossing edges ("can be embedded in the plane"). Kₙ, for instance, is not planar.

Leading us to Q1: I give you G. How hard is it to decide if it's planar?

3/7
Read 7 tweets
Clément Canonne Profile picture
23 Jul
📊 It's Thursday: time for our wÆkly quiz! I'll build a little bit on last week's statistics/algorithms thread (see below for a recap), and ask you two 2️⃣ questions.

General topic: testing distributions, "leaky" measurements, and adaptivity. 🔍

1/6
Suppose you have the following type of measurements: at each time step, you get to specify a subset S⊆[k], your "question"; and *try* to observe a fresh sample x from the unknown distribution p (over [k]). With probability η, you get to see x: it's leaked to you 🎁...

2/6
... but with probability 1-η, you only get to know if x is in S. (Think of it as yes/no ❓, but w/ an η chance to get full info 🎁.)

We'll fix η=1/√k: you don't win 🎁. often. Your goal: test if p is uniform, or at large statistical distance (TV) from uniform, say 1/100.

3/6
Read 6 tweets

Did Thread Reader help you today?

Support us! We are indie developers!

This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!

Follow Us on Twitter!

Like this author's thread?

Get emails when @ccanonne_ has new unrolls!

Check out other threads from @ccanonne_!

Read all threads by @ccanonne_