Greatest common divisor

java

Built-in

1
2
3
4
5
import java.math.BigInteger;

public static long gcd(long a, long b) {
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}

Recursive

To calculate \( gcd(m, n) \), for given values \( 0 \leq m < n\), Euclid’s algorithm uses the recurrence

\(
\begin{align*}
\begin{cases}
gcd(0, n) = n ; \\
gcd(m, n) = gcd(n \hspace{1mm} mod \hspace{1mm} m, m), \hspace{4mm} for \hspace{1mm} m > 0. \\
\end{cases}
\end{align*}
\)

for example, \( gcd(12, 18) = gcd(6, 12) = gcd(0, 6) = 6 \).

1
2
3
4
5
6
7
8
9
public static long gcd(long a, long b) {
if (a == 0)
return b;
if (b == 0)
return a;
if (a > b)
return gcd(b, a % b);
return gcd(a, b % a);
}

non mod

1
2
3
4
5
6
7
8
public static long gcd(long a, long b) {
if (a < b)
return gcd(b, a);
if (b == 0)
return a;
else
return gcd(a - b, b);
}

bit operation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static long gcd(long a, long b) {
if (a < b)
return gcd(b, a);
if (b == 0)
return a;
else {
if ((a & 1) == 0) {
if ((b & 1) == 0)
return (gcd(a >> 1, b >> 1) << 1);
else
return gcd(a >> 1, b);
} else {
if ((b & 1) == 0)
return gcd(a, b >> 1);
else
return gcd(b, a - b);
}
}
}

references

[趣味数学·益智游戏]魔方

鲁比克教授当年以帮助学生理解3D几何中的空间转动为动机而构想的教学道具却无心插柳地成为有史以来最畅销的机械益智玩具。

  一个外围26个子块的内部铰接构造能使其任意一面都可以随意旋转(任意方向可转90度或半圈)的3×3×3六面体。六个面颜色互异,这个玩具的目标是在经过任意次随机扭转后复原六面单色的状态。这个在20世纪七十年代由匈牙利人艾尔诺•鲁比克发明的机械益智玩具在随后的八十年代期间卖出了数百万个。

  鲁比克魔方的变换总数达

\( \huge \frac{8! * 12! * 3^8 * 2^{12}}{2 * 3 * 2} = 43252003274489856000 \)

(特纳&戈尔德,1985,Schönert)。霍伊使用波利亚-伯恩赛德引理证明了存在针对魔方整体对称性共轭不变的 901083404981813616 种不同变换。

  鲁比克魔方的转动操作内蕴的有限群称为鲁比克群,鲁比克群的凯莱图称为鲁比克图,复原任意颜色组合的魔方所需要的最少转动次数等于鲁比克图的直径(即最长测地线),有时被称为上帝之数。尽管存在从任意颜色组合复原魔方的算法,它们不一定是最优的(即最少的转动次数),计算上帝之数异常困难,早在1995年就已经知道上帝之数的下界(在最坏的情形)是20。直到2010年托马斯•罗基奇等人证明任意颜色组合的魔方都能够在20步内复原[1],从而确立上帝之数为20

另见:

上帝之数,鲁比克钟,鲁比克图,鲁比克群

参考:

  • G.赫尔姆斯,鲁比克魔方
  • D.霍伊,魔方的问题空间/解空间的实际测度
  • 道格拉斯•理查•霍夫斯塔特[2],魔方迷玩转魔方,魔方大师破解魔方,《科学美国人》第244期Metamagical Themas专栏, 20-39页, 1981年3月
  • 道格拉斯•理查•霍夫斯塔特,不可思议的元主题:心灵与模式的追问,第14章,位于纽约的BasicBooks出版社, 1985
  • 赫伯特•科先巴,最优解
  • M.E.拉森,魔方的报复:群论解决方案,美国数学月刊第92期,381-390,1985
  • M.朗里奇,魔方的领域
  • D.L.W.米勒,用最快的搜索算法和简要表解决鲁比克方块
  • J.帕尔默,魔方路线,新科学家第199期,40-43,2008
  • 托马斯•罗基奇,25步足以复原魔方,2008年3月24日
  • 托马斯•罗基奇,22步足以复原魔方,2008年8月12日
  • 托马斯•罗基奇 & 赫伯特•科先巴 & 莫利•戴维森 & 约翰•德斯里奇,上帝之数是20
  • Jaap Scherphuis,Jaap的荟萃益智玩具的专题网页:3×3×3鲁比克方块
  • M.Schoenert,魔方爱好者: 按日期索引
  • M.Schönert,用GAP计算群论方法分析魔方
  • D.Singmaster,鲁比克魔方札记,位于新泽西州Hillside的Enslow出版公司,1981
  • 唐•泰勒,精通鲁比克方块,位于纽约的HRW(Holt, Rinehart, and Winston)教育图书出版公司,1981
  • 唐•泰勒 & 莲妮•赖兰兹,魔方游戏:92个玩法和解法,位于纽约的HRW(Holt, Rinehart, and Winston)教育图书出版公司,1981
  • E.C.特纳 & K.F.戈尔德,鲁比克群,美国数学月刊第92期,617-629,1985

[1] 与四色定理一样,证明上帝之数等于20使用的方法也是求助于现代计算机威力的蛮力法,因此这并不是一个符合美学标准的证明

[2] 侯世达(中文名),曾获得普利策奖的《哥德尔、埃舍尔、巴赫:集异璧之大成》一书的作者


原文:Rubik’s Cube

Lines

by Emily Jane Brontë

I die, but when the grave shall press
The heart so long endeared to thee,
When earthly cares no more distress
And earthly joys are nought to me,

Weep not, but think that I have passed
Before thee o’er a sea of gloom,
Have anchored safe, and rest at last
Where tears and mourning cannot come.

‘Tis I should weep to leave thee here
On the dark ocean sailing drear,
With storms around and fears before,
And no kind light to point the shore.

But long or short though life may be,
‘Tis nothing to eternity:
We part below to meet on high,
Where blissful ages never die.

LeetCode - Algorithms - 509. Fibonacci Number

\( F_n = F_{n-1} + F_{n-2} \)

\( F_0 = 0, F_1 = F_2 = 1 \)

Problem

509. Fibonacci Number

a “toy” problem. It’s easy to understand and maybe surprising that there are many different solutions.

Java

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int fib(int N) {
int r=0;
if (N == 0)
r = 0;
if (N == 1)
r = 1;
if (N > 1)
r = fib(N - 1) + fib(N - 2);
return r;
}
}

Submission Detail

  • 31 / 31 test cases passed.
  • Runtime: 14 ms, faster than 5.42% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36.1 MB, less than 5.51% of Java online submissions for Fibonacci Number.

Dynamic Programming

Using dynamic programming in the calculation of the nth member of the Fibonacci sequence improves its performance greatly.

bottom-up approach

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int fib(int N) {
if (N == 0)
return 0;
int previousFib = 0, currentFib = 1;
int newFib = 0;
for (int i = 1; i < N; i++) {
newFib = previousFib + currentFib;
previousFib = currentFib;
currentFib = newFib;
}
return currentFib;
}
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 35.8 MB, less than 36.87% of Java online submissions for Fibonacci Number.

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int fib(int N) {
int r=0, recip1st=0, recip2nd=1;
if (N == 0)
r = 0;
if (N == 1)
r = 1;
for(int i=1; i<N; i++) {
r = recip1st + recip2nd;
recip1st = recip2nd;
recip2nd = r;
}
return r;
}
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36.6 MB, less than 5.51% of Java online submissions for Fibonacci Number.

top-down approach

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.HashMap;
import java.util.Map;

class Solution {
public int fib(int N) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, 0);
map.put(1, 1);
map.put(2, 1);
map.put(3, 2);
map.put(4, 3);
map.put(5, 5);
map.put(6, 8);
map.put(7, 13);
map.put(8, 21);
map.put(9, 34);
map.put(10, 55);
map.put(11, 89);
map.put(12, 144);
map.put(13, 233);
map.put(14, 377);
map.put(15, 610);
map.put(16, 987);
map.put(17, 1597);
map.put(18, 2584);
map.put(19, 4181);
map.put(20, 6765);
map.put(21, 10946);
map.put(22, 17711);
map.put(23, 28657);
map.put(24, 46368);
map.put(25, 75025);
map.put(26, 121393);
map.put(27, 196418);
map.put(28, 317811);
map.put(29, 514229);
map.put(30, 832040);
if (!map.containsKey(N))
map.put(N, fib(N - 1) + fib(N - 2));
return map.get(N);
}
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36 MB, less than 25.69% of Java online submissions for Fibonacci Number.

2

As constraints 0 <= n <= 30

1
2
3
4
5
6
class Solution {
public int fib(int N) {
int[] table = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040};
return table[N];
}
}
Submission Detail
  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 35.7 MB, less than 69.84% of Java online submissions for Fibonacci Number.

formula

golden ratio \(\huge \varphi = \frac{1 + \sqrt{5}}{2} \)

\(\LARGE F_n = \frac{\varphi^n-(1-\varphi)^n}{\sqrt{5}} \)

This solution is often used as a standard example of the method of generating functions.

1
2
3
4
5
6
7
class Solution {
public int fib(int N) {
final double SQRT5 = Math.sqrt(5);
Double d = ( Math.pow((1+SQRT5)/2,N)-Math.pow((1-SQRT5)/2,N) )/SQRT5;
return d.intValue();
}
}

Submission Detail

  • 31 / 31 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
  • Memory Usage: 36.2 MB, less than 5.51% of Java online submissions for Fibonacci Number.

Why is Euler's phi function multiplicative?

In number theory, Euler’s totient function, also be called Euler’s phi function \( \varphi(n) \) counts the positive integers up to a given integer n that are relatively prime to n.

\( \varphi(1)=1 \)

\( \varphi(mn)=\varphi(m)\varphi(n) \hspace{16 pt} whenever \hspace {8pt} m \bot n \hspace {8pt} i.e. \hspace {8pt} gcd(m, n)=1 \)

Si sint A et B numeri inter se primi et numerus partium ad A primarum sit = a, numerus vero partium ad B primarum sit = b, tum numerus partium ad productum AB primarum erit = ab. - L. Euler

Outline of proof: let A, B, C be the sets of nonnegative integers, which are, respectively, coprime to and less than m, n, and mn; then there is a bijection between A × B and C, by the Chinese remainder theorem.


Concrete Mathematics p144
NUMBER THEORY - Exercises - Warmups - 10 Compute \( \phi(999) \).

\( \phi(p)=p-1 \)

\( \phi(p^k)=p^k-p^{k-1} \)

\( \phi(999)=\phi(3^3 \times 37) \)

\( =\phi(3^3) \times \phi(37) = (3^3-3^2) \times 36 = 648 \)


\( \phi(666) = 216 = 6 \times 6 \times 6 \)


What we do (and don't) know about the coronavirus - David Heymann - Transcript

As of the morning February 27, 2020, there were at least 82,000 confirmed cases worldwide of the coronavirus and 2,810 deaths from it. TED invited Dr. David Heymann to share the latest findings about the outbreak.


What happens if you get infected with the coronavirus?

如果你感染了新冠病毒, 症状是什么?

This looks like a very mild disease, like a common cold, in the majority of people. There are certain people who get infected and have very serious illness; among them are health workers. It’s a very serious infection in them, as they get a higher dose than normal people, and at the same time, they have no immunity. So in the general population, it’s likely that the dose of virus that you receive when you are infected is much less than the dose that a health worker would receive, health workers having more serious infections. So your infection would be less serious, hopefully. So that leaves the elderly and those with comorbidities to really be the ones that we have to make sure are taken care of in hospitals.

大多数人的症状显得轻微,就像普通的感冒。但有一些感染者,会表现出非常严重的症状,这些人中包括医护人员。对他们来说,这种感染非常严重,因为他们接触的病毒量比起普通人要高得多,与此同时,他们没有足够的免疫力。在普通人群中,大致上你受感染时接触的病毒量远低于一位医护人员所接触到的病毒量,许多医护人员会遇到更严重的感染。所以普通人若被感染,也不会特别严重,但愿如此。剩下的就是老人和患有并发症的人,他们是我们必须确保 得到医院治疗的人。

Who are the people who should be most concerned about this?

哪些人特别需要重视这个病毒?

Well, the most concerned are people who are, first of all, in developing countries and who don’t have access to good medical care and may not have access at all to a hospital, should an epidemic occur in their country. Those people would be at great risk, especially the elderly. Elderly in all populations are at risk, but especially those who can’t get to oxygen. In industrialized countries, it’s the very elderly who have comorbidities, who have diabetes, who have other diseases, who are at risk. The general population doesn’t appear to be at great risk.

最应该重视此事的人,首先是那些处于发展中国家,缺少优质医疗资源,甚至可能无法前往医院的人。当流行病毒波及他们的国家时,他们需要特别注意。那些人,特别是其中的老年人,将面临高风险。 所有人口中的老年人都面临风险,尤其是那些无法得到氧气供应的人。在工业化国家,那些有并发症、糖尿病和其他疾病的老年人都面临风险。现在看来,普通人群则风险不大。

What pre-existing medical conditions put people at higher risk?

有哪些既存病症会使人们面临更高的感染风险?

First of all, pulmonary disease existing as a comorbidity is also important. In general, the elderly are at greater risk, especially those over 70, because their immune systems are not as effective as they might have once been, and they are more susceptible to infections. In addition, in some instances in China, there’s been a coinfection with influenza and at the same time, there have been some bacterial superinfections on the pneumonias that are occurring.

首先,已患有肺病并发症的人要引起重视。总体来说,老年人患病风险是最高的,特别是 70 岁以上的老人,因为他们的免疫系统不如年轻时那样强健,所以他们更容易受到感染。而且,在中国的一些病例存在新冠和流感的共同感染,与此同时,还有肺炎上的细菌重复感染。

Where can we find up-to-date information?

我们能从哪里获得最新信息?

The Center for Disease Control in Atlanta keeps track and has updates on a regular basis on its website. Also, the World Health Organization in Geneva, which is coordinating many of the activities going on internationally, also has a website with daily updates. It’s our responsibility to get that information as individuals, so we understand and can make sure that we can contribute in our own way to prevention of major spread.

亚特兰大的疾病控制与预防中心(CDC)会在它的网站上定期更新追踪到的疫情信息。位于日内瓦的世界卫生组织正在协调全球同时开展的许多行动,也会在自己的网站上每日更新。我们每个人都有责任 去获取那些信息,以便了解 并确知如何各尽所能 阻挡疫情的大范围传播。

You led the global response to the SARS outbreak in 2003. How does this outbreak compare?

在 2003 年,全球抗击 SARS 病毒的行动由你领导,相对而言,如何评价这次的疫情爆发?

That’s the same problem with all new infections. This is an infection that’s coming to humans who have never been exposed to this virus before. They don’t have any antibody protection, and it’s not clear whether their immune system can handle this virus or not. This is a virus that usually finds itself in bats or in other animals, and all of a sudden, it’s in humans. And humans just don’t have experience with this virus. But gradually, we are beginning to learn a lot, as we did with SARS. And you know, there are certainly a larger number of deaths than there were with SARS. But when you divide that by a denominator of persons who are infected, there are many, many more persons infected than there were with SARS. The case fatality ratio, that is the ratio of deaths to the numbers of cases in SARS, was about 10 percent. With the current coronavirus, COVID-19, it is two percent or probably less. So it’s a much less virulent virus, but it’s still a virus that causes mortality, and that’s what we don’t want entering human populations.

所有的新型感染的问题都一样。人类之前从未暴露于这种病毒之中。人类没有任何抗体的保护,现在还无法确定人体本身的免疫系统是否可以抵抗这个病毒。这种病毒一开始传播于蝙蝠或其他动物之间, 突然,它出现在了人类中。人类对它没有任何处理经验。但渐渐的,我们开始整理出头绪,就像当时面对 SARS 病毒一样。大家也知道,这个病毒的死亡人数超过了 SARS 病毒。 但是若用死亡人数除以所有感染的人数 —— 新冠感染人数也比感染 SARS 病毒的人多 —— 对比死亡率,即死亡人数和确诊人数的比例,就 SARS 而言,是 10% 左右。对于新冠病毒(COVID-19)来说, 现在的死亡率低于 2%。 所以它是一种毒性偏低的病毒,但仍是一种可致命的病毒, 我们非常不希望它进入人群中。

Have we responded adequately at border crossings, such as airports?

我们在国家边境做出的措施 还算及时妥当吗?

It’s clearly understood that airports or any land borders cannot prevent a disease from entering. People in the incubation period can cross that border, can enter countries and can then infect others when they become sick. So borders are not a means of preventing infections from entering a country by checking temperatures. Borders are important because you can provide to people arriving from areas that might be at risk of having had infection, provide them with an understanding, either a printed understanding or a verbal understanding, of what the signs and symptoms are of this infection, and what they should do if they feel that they might be infected.

我们现在很清楚的认识到,机场和其他的陆地边境并不能阻止病毒的入侵。 处于潜伏期的病患仍可以出入边境,出入国境,并在病发后传染他人。因此,若仅通过检测体温 防止病毒进入一个国家,边境限制并不算是一种防疫机制。边境非常重要,因为可以为那些来自病毒高风险地区的人们提供书面或是口头的讯息,让他们了解感染病毒后会产生哪些症状,若他们感觉自己可能被感染后,可以采取什么措施。

What’s the timeline for a vaccine?

现在疫苗研发的时间线是怎么样的?

Vaccines are under development right now, there’s a lot of research going on. That research requires first that the vaccine be developed, then that it be studied for safety and effectiveness in animals, who are challenged with the virus after they are vaccinated, and then it must go into human studies. The animal studies have not yet begun, but will soon begin for certain vaccines. And it’s thought that by the end of the year, or early next year, there may be some candidate vaccines that can then be studied for licensing by regulatory agencies. So we’re talking about at least a year until there’s vaccine available that can be used in many populations.

目前相关疫苗正在研发当中,很多研究正在进行。目标首先是研发出一种疫苗,再是观察研究疫苗在动物身上的安全性和效力,让动物接种疫苗后再接触病毒,然后必须进行人体研究。现在,动物试验还未开始,但马上就会有几株疫苗开始进行试验。我们期望在今年年底或明年年初完成针对一些备选疫苗的研究并取得监管部门派发的使用许可证。现在可预计的是至少需要一年的时间才能研发出可被多人群接种的疫苗。

What questions about the outbreak are still unanswered?

哪些有关疫情的疑问仍有待回答?

It’s clear we know how it transmits, we don’t know how easily it transmits in humans, in communities or in unenclosed areas. We know, for example, that in the enclosed area of a cruise ship, it spread very easily. We need to better understand how it will spread once it gets into more open areas where people are exposed to people who might be sick.

现在我们清楚病毒的传播途径, 但我们还不知道病毒在人群中、在社区中或是在未封闭环境中有多容易传播。我们知道的是,在一个相对封闭的环境中,比如说游轮上,病毒传播得非常快。我们需要更好的理解病毒在更开放空间中是如何传播的, 特别是当人们接触到可能感染的患者时。

What about the global response could be improved?

全球对于病毒的应对有哪些可以改进的地方?

A major problem in the world today is that we look at outbreaks in developing countries as something that we need to go and stop. So when there’s an outbreak of Ebola, we think “How can we go and stop this outbreak in the country?” We don’t think about “How can we help that country strengthen its capacity, so that it can detect and respond to infections?” So we haven’t invested enough in helping countries develop their core capacity in public health. What we’ve done is invested in many mechanisms globally, which can provide support to other countries to go and help stop outbreaks. But we want to see a world where every country can do its best to stop its own outbreaks.

当今世界上一个很严重的问题在于,当我们关注在发展中国家的病毒爆发时,我们会想到要去当地消灭病毒。当埃博拉病毒爆发时,我们想的是,“我们如何在那里阻止病毒的传播?”而不是“我们如何帮助那个国家提高整体医疗水平,以有效检测和应对感染?” 所以在帮助其他国家提高公共医疗水平方面,我们并没有进行足够的投资。我们所做的是投资全球的许多应对机制,从而为其他国家提供帮助,阻止病毒的传播。但我们更希望看到的是所有国家能尽自己最大的努力来阻止病毒的爆发。

Will we see more emerging disease outbreaks in the future?

在未来我们是否会经历更多的疫情爆发?

Today, there are over seven billion people. And when those people come into the world, they demand more food, they demand a whole series of things and they live closer together. In fact, we’re an urban world, where people live in urban areas. And at the same time, we’re growing more animals, and those animals are contributing food to humans as well. So what we see is that that animal-human interface is becoming closer and closer together. And this intensive agriculture of animals and this intensive increase in human populations living together on the same planet is really a melting pot where outbreaks can occur and do occur. We will eventually have more and more of these outbreaks. So an emerging infection today is just a warning of what will happen in the future. We have to make sure that that technical collaboration in the world is there to work together to make sure that we can understand these outbreaks when they occur and rapidly provide the information necessary to control them.

今天,地球上有超过 70 亿人口。人口增长带来的是对食物和生活用品日益增长的需求,而且在生活中,人们彼此的距离会越来越近。现在的世界,是城市化的世界,大多数人住在城市地域。与此同时,我们也饲养越来越多的牲畜,这些牲畜是人类的食物来源。我们发现,动物和人类的交界也在变得越来越近。畜禽集约农业以及极速上升的人口在同一个星球上共存,这种大熔炉式的生活方式 让疫情爆发成为了可能。这样的疫情爆发还会越来越多。当今的疫情为未来将会发生什么敲响了警钟。我们必须确保世界范围内的技术合作在病毒爆发时能够帮助我们了解疫情的发展,并迅速提供必要的信息进行有效防控。

Is the worst behind us?

最糟的时候已经过去了吗?

I can’t predict with accuracy. So all I can say is that we must all be prepared for the worst-case scenario. And at the same time, learn how we can protect ourselves and protect others should we become a part of that epidemic.

我无法准确回答这个问题。我能说的是,我们必须为最坏情况做好准备。与此同时,若我们被卷入这场疫情中,要学会如何保护自己和他人。

VS Code Shortcuts

Toggle word wrap

Alt + Z

Code Formatting

  • On Windows: Shift + Alt + F
  • On Mac: Shift + Option + F
  • On Ubuntu: Ctrl + Shift + I

Navigate to a Specific Line

  • On Windows: Ctrl + g
  • On Mac:Ctrl + g or Ctrl + p
  • On Ubuntu: Ctrl + g

Deleting a Line

  • On Windows: Ctrl + x
  • On Mac: Command + x
  • On Ubuntu: Ctrl + x

select current line

  • One Mac: Command + L

switch text case

  • On Mac: Command + P, then type >transform

ref