Free Fibonacci Sequences

John Conway likes playing with the Fibonacci sequence. He invented many new sequences using the following trick. The next number in the sequence is the sum of the two previous number adjusted in some way. Free Fibonacci sequences were invented this way. Here is the recurrence for an n-free Fibonacci sequence: the next number in the sequence is the sum of the previous two numbers divided by the highest possible power of n.

Let us calculate a 2-free Fibonacci sequence starting with 5 and 4: 5, 4, 9, 13, 11, 3, 7, 5, 3, 1, 1, 1, …. I leave it to the reader to show that any 2-free sequence ends with a cycle of length one.

Let us try a 3-free Fibonacci sequence starting with 5 and 6: 5, 6, 11, 17, 28, 5, 11, 16, 1, 17, 2, 19, 7, 26, 11, 37, 16, 53, 23, 76, 11, 29, 40, 23, 7, 10, 17, 1, 2, 1, 1, 2, and so on. We are now in the cycle of length 3. Is this always the case? Not quite. If there is a 1-1-2 cycle there should be a 2-2-4 cycle, or any cycle k-k-2k, where k is coprime with 3. But the question remains: does it always end in a cycle of length 3?

I published a paper Free Fibonacci Sequences with Brandon Avila. We conjecture that a 3-free Fibonacci sequence always ends in a cycle and support this conjecture with a probabilistic argument. We were amused by how the behavior changes when we move to 4-free Fibonacci sequences. It seems that in this case sequences never cycle. We were even more amused when we moved to 5-free Fibonacci sequences and discovered that the behavior changes again.

When n equals 5 there are some sequences that cycle. Can you find the cycles? There are also sequences that grow indefinitely and we do not need a probabilistic argument to prove that. Consider Lucas numbers: 2, 1, 3, 4, 7, 11, and so on. This is a Fibonacci-like sequence that never has a term divisible by 5. Thus Lucas numbers form a 5-free Fibonacci sequence. We made a probabilistic argument that most of the starting terms converge eventually to a Lucas-like sequence that grows indefinitely because there are no terms divisible by 5.

What happens for larger n? We didn’t manage to find any cycles there. Would you like to try?


Stuck at 225

My weight loss progress is progress no more. I am stuck at 225.

I have my morning routine. I wake up and jog to the facilities; then I weigh myself. Why do I do this in this order? Because I do not use an alarm-clock. I depend on my own hydro-alarm that wakes me up every morning very reliably. The downside is that this alarm doesn’t have a snooze button. I just have to get up, and get up very fast. So I have to relieve myself first; then I can weigh myself calmly. As a collateral benefit, by availing myself first, I get a slightly better result.

While weighing myself every day, I noticed some patterns. My weight is slightly better if I get a long night of sleep. I guess my availing is more voluminous then.

Another pattern that I noticed is that if I do not eat after 5:00 pm, I do not gain weight and sometimes I lose a bit; if I do eat after 5:00 pm, even a very light dinner, I can gain up to 3 pounds. This becomes a struggle and sometimes hunger wins. So I stick to the plan for three weeks, and then one moment of tiredness and hunger, one dinner, and, boom, I am back where I was.

This is even affecting my social life. I stopped inviting friends and family for dinner and I am tense whenever I visit my friends in the evening.

The surprising thing is that my system worked at the beginning. I keep asking myself what the difference is. I think I was strongly motivated and excited about my weight loss plan. It’s impossible to sustain that level of excitement, so I’ve adopted a new element in my plan. I decided to replace my initial excitement by external motivation. I am now listening to motivational tapes in my car. We’ll see.


De-stressing Jokes

Whenever I am under stress, I turn to jokes. My recent problems with spam attacks on my blog led me to surf the web for new math jokes. Here are some of my recent translations from Russian.

* * *

Two is the same thing as eight, to some degree.

* * *

A girl to her mathematician boyfriend:
— Let’s do something that is forbidden tonight.
— Divide by zero?

* * *

If thoughts converge, they are bounded.

* * *

A mathematician’s son:
— Dad, how do I write the number 8?
— That’s easy: rotate the infinity symbol by pi over 2.

* * *

My student couldn’t take an integral from my book. So he took the book together with all the integrals there.

* * *

Archimedes, Pascal and Newton play hide and seek. Archimedes is the seeker. Pascal hides, but Newton draws a 1-meter square around himself. Archimedes opens his eyes and shouts:
— I see Newton!
— Oh, no! One newton per square meter is the pascal.

* * *

What a pleasure to smoke an e-cigarette after cybersex…

* * *

Russians were the first in the world to create a computer program that passes the Turing test. Scientists tested the program using several Russians with a variety of questions, and each time the program gave the same answer as the people. The reply to every question was, “Go f*ck yourself!”

* * *

There are two types of people: those who know nothing about fractals and those who think that there are two types of people: those who know nothing about fractals and those who think that there are two types people…


My Blog is under Attack

My readers noticed that my blog disappeared several times. Here’s what’s been happening. Spammers were sending tens of thousands of comments a day, which crashed the server several times. My hosting provider couldn’t handle it and took down my blog. They asked me to install CAPTCHAs.

Installing CAPTCHAs became a big issue. Since I started my blog in 2008 I’ve never bothered to update the WordPress software. As a result, all the CAPTCHA plugins I tried to install wouldn’t work. I had no choice but to update WordPress. After so many years, this would surely not be a simple matter. So I decided to hire someone to help. It took me a month to find Brett Mellor, but finally he updated my WordPress software.

Updating such an old database starts with a backup. We didn’t want to back up all the tens of thousands of spam comments, but we couldn’t sort through them, because my hosting provider was blocking the user-friendly access to my blog. We were forced to delete all the new comments. In the process, I’ve lost some of the legitimate comments as well. I apologize for that. If you do not see your comments, please resubmit.

In addition, we had to re-number all the categories, so the old category links no longer work.

I was paralyzed by all the stress of not only losing access to my blog, but also not knowing how to solve the problem. This prevented me from writing for three months, and for this I apologize as well.

Now my blog is updated and CAPTCHAs are installed. I’ve gone from 50,000 spam comments per day to 500. However, my hosting provider still complains about unusual activity and spam comments.

Your brilliant suggestions are very welcome.


My Ancestry

I always wanted to be a person of the world. I wanted my genes to be a mixture of everything. I was glad that I had a great-grandfather from Poland and a great-great-great-grandmother from France. I was also thrilled when my mom told me that her Asian students think she is one of theirs. So I decided to send my DNA to 23andMe and really see what I have.

To my surprise, my world is not as mixed as I expected: I am 99.5% European. My Asian part is minuscule: 0.2%, out of which only 0.1% is assigned as Yakut. My African part is also 0.2%.

My European part is a mixture of mostly eastern and northern European. I am 2.8% Ashkenazi.

My Ancestry

In addition to my genetic profile, 23andMe sent me the list of a thousand of my distant relatives. They also sent me a report about the most common last names among my relatives. The list starts with Cohen and continues with Levine, Levin, Goldberg, and Rubin.

You might be surprised by this list of Jewish names when I am only 2.8% Jewish. But the list is based on people who decided to send their DNA to 23andME and provided their last names. All my Russian relatives remained in Russia. Russia has its own company, I-gene, that provides a similar service, and the two databases are not shared.

Only my distant relatives who moved to the US and who are curious about their ancestry and who are willing to share their last names will appear on this list. So maybe this list is not surprising.


No Averages

Here is an old Olympiad problem:

Prove that you can choose 2k numbers from the set {1, 2, 3, …, 3k−1} in such a way that the chosen set contains no averages of any two of its elements.


Lazy Jokes

* * *

—Describe yourself in three words.

* * *

Internet forum:
—Tell me about yourself.
—I am lazy and I like to eat.
—Tell me some more.
—I am tired of typing. I’ll go grab a snack.

* * *

—Why do you want to divorce your wife?
—She nags too much. For the last half six month, she’s been bugging me everyday to throw away the Christmas tree.

* * *

Yesterday I realized that I’m not the laziest person in the world. I saw my neighbor walking the dog on a leash through his window.

* * *

The list of symptoms of laziness:


A Logic Quiz

This is a variation on an old quiz. Can you answer the last question?

—An airplane carries 500 bricks. One of the bricks falls out. How many bricks are left in the airplane?
—This is easy: 499!
—Correct. Next question. How do you put a giraffe into a refrigerator?
—Open the refrigerator, put in the giraffe, and close the refrigerator door.
—Good, next. How do you put an elephant into a refrigerator?
—Open the refrigerator, take out the giraffe, put in the elephant and close the door.
—Correct. The Lion King is hosting his birthday party. All the animals come to congratulate him—except one. Why?
—The elephant couldn’t come because it is in the refrigerator.
—Fantastic, next. A man needs to cross a river inhabited by crocodiles and he doesn’t have a boat. What should he do?
—He can just swim: all the crocodiles are attending Lion King’s birthday party.
—Amazing! The last question: The man swims across the river, and dies. What happened?


ApSimon’s Mints

Hugh ApSimon described the following coin puzzle in his book Mathematical Byways in Ayling, Beeling and Ceiling.

New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material: fake coins weigh the same independently of the mint. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings so that you can deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?

I will follow ApSimon’s notation. Suppose Pr and Qr is the number of coins from the mint r used in the first and the second weighing correspondingly. That is, we are minimizing Σmax(Pr,Qr). (All my summations are over all the mints. I skip the summation limits because it is difficult to write math in html.) Let us denote by W the weight of the genuine coin and by W(1 + ε) the weight of the fake coin. We do not know ε, except that it is not zero.

Let dr be either 0 or 1, depending on what material the r-th mint uses. Thus, the coin from the r-th mint weighs W(1 + drε). We know the results of these two weighings and the weight of the genuine coin. Therefore, we can calculate the following two values: a = ΣPrdrε and b = ΣQrdrε.

It is clear that we need to request at least one coin from each mint and use it in at least one weighing: Pr + Qr > 0. If both sums a and b are zero, then all the mints are producing genuine coins. Neither of the two values gives us much information as we do not know ε. We can get rid of ε by dividing a by b.

There are 2n − 1 combinations of possible answers: these are subsets of the set of mints producing fake coins given that there is at least one. Thus we need to select numbers Pr and Qr, so that a/b produces 2n − 1 possible answers for different sets of values of dr.

Let us consider cases in which the total number of mints is small. If there is one mint we can take one coin and we won’t even need a second weighing. For two mints we need one coin from each mint for a total of 2. For three mints, one coin from each mint is not enough. I leave this statement as an exercise. It is possible to test three mints with four coins: one each from the first and second mints and two from the third mint. The coins from each mint for the first and second weighings are (0,1,2) and (1,1,0) respectively.

To prove that this works we need to calculate (d2 + 2d3)/(d1 + d2) for seven different combinations of dr. I leave this as an exercise.

This puzzle seems to be very difficult. We only know the answer if the number of mints is not more than seven. The corresponding sequence A007673 in the OEIS is: 1, 2, 4, 8, 15, 38, 74. It is possible to give bounds for this sequence, but they are so far apart. The lower bound is n. And the ApSimon’s book offers a construction for two weighings were Pr = r! and Qr = 1.

You can try to find a better construction, or you can try calculating more terms of the sequence. You can also read more about this problem in my short paper Attacking ApSimon’s Mints.

I do not want to leave the readers with the puzzle that might end up being intractable. So I suggest the following easy puzzle. Solve the ApSimon’s Mints problem assuming that the weight of the fake coin is known.


Masturbating With an Accent

I once took an accent reduction course, to modify my Russian accent in English. In the first class the teacher explained that the biggest reason people have strong accents is that they stop learning and trying to improve their speech as soon as they can be understood. I promised myself to never stop learning and to continue working on my accent reduction forever.

Once I was giving a lecture on probability and statistics at the IAP mathematical series. My last slide was about the research on the correlation between masturbation male habits and prostate cancer. Their interpretation of the data had been wrong and a very good example of what not to do.

So I looked directly into the eyes of the course coordinator, who was observing my lecture, and without realizing what I was saying, asked, “Do we have time for masturbation?”

Everyone started laughing and I had to present my slide in order to explain myself.

The news of my double entendre spread. Soon after that I was asked to give a lecture at the Family Weekend at MIT. I wonder if that is why the lecture coordinator asked me not to discuss masturbation as small children might be present.

Luckily that was the only fallout from my blooper. Anyway, I decided to stop working on my accent. When people understand that English is not my first language they forgive more readily my slips of tongue.