# \[Numberphile\] - Amazing Graphs III

**URL:** <https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635>\
**Category:** Staff Picks\
**Tags:** fun-and-play, mathematica, discrete-mathematics, graphics-and-visualization, computer-based-maths, staff-pick\
**Created:** [August 22, 2019, 6:36pm UTC](https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635 "2019-08-22T18:36:19Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![sghuisman](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/sghuisman/32/27850_2.png) [@sghuisman](https://community.wolfram.com/u/sghuisman)\
**Post date:** [August 22, 2019, 6:36pm UTC](https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635/1 "2019-08-22T18:36:19Z")

</div>

This is part of a series where I explore some of the videos of Numberphile, see also the other ones:

- [[Numberphile] - The Illumination Problem](https://wolfram.discourse.group/t/10253/1)
- [[Numberphile] - Frog Jumping - Solving the puzzle](https://wolfram.discourse.group/t/10284/1)
- [[Numberphile] - Sandpiles - Done in the Wolfram Language](https://wolfram.discourse.group/t/10307/1)
- [[Numberphile] - The Square-Sum Problem](https://wolfram.discourse.group/t/11808/1)
- [[Numberphile] - How to make a binary prime logo](https://wolfram.discourse.group/t/10307/1)
- [[Numberphile] - Amazing Graphs II](https://wolfram.discourse.group/t/14591/1)

Today we are gonna look at another video on graphs: [https://www.youtube.com/watch?v=j0o-pMIR8uk](https://www.youtube.com/watch?v=j0o-pMIR8uk)

The first sequence ([A002487 - OEIS](https://oeis.org/A002487)) can, conveniently be recreated by using `Riffle`:

```
data = NestList[Riffle[#, Total /@ Partition[#, 2, 1]] &, {1, 1}, 13];
data = Join @@ data[[All, ;; -2]];
ListPlot[data]

```

 ![Screenshot2019-08-22at20.18.27.png](https://global.discourse-cdn.com/wolfram/original/2X/7/7571b009058fb7776600f2ad03ee2e079c5343e0.png)

The second sequence ([A005185 - OEIS](https://oeis.org/A005185)) can be recreated like this:

```
Dynamic[i]
n = 100000;
x = ConstantArray[1, n];
Do[
 os = {x[[i - 2]], x[[i - 1]]};
 tot = x[[i - os]];
 x[[i]] = Total[tot];
 ,
 {i, 3, n}
 ]

```

giving:

 ![Screenshot2019-08-22at20.21.49.png](https://global.discourse-cdn.com/wolfram/original/3X/9/1/91fdf262a72615dbe423041b54a312017c66a4aa.png)

An alternative view would be to plot it logarithmically in the horizontal direction, and to divide the sequence by the index of each number:

```
tmp = N[x];
tmp /= Range[Length[tmp]];
ListLogLinearPlot[tmp, PlotRange -> All]

```

 ![Screenshot2019-08-22at20.23.09.png](https://global.discourse-cdn.com/wolfram/original/3X/6/3/6324b2eade5e2ab11d375ba459b632d42d5e86e1.png)

The last sequence ([A279125 - OEIS](https://oeis.org/A279125)) can be recreated like this:

```
n=1000;
x=ConstantArray[0,n];
Dynamic[i]
Do[
 k=-1;
 ok=False;
 While[!ok,
  k++;
  good=True;
  Do[
   If[x[[j]]==k,
    If[BitAnd[i,j]>0,
     good=False;
     Break[];
    ]
   ]
  ,
  {j,1,i-1}
  ];
  If[good==True,
   x[[i]]=k;
   Break[];
  ]
 ]
,
 {i,2,n}
]
ListPlot[x]

```

giving:

 ![Screenshot2019-08-22at20.25.30.png](https://global.discourse-cdn.com/wolfram/original/3X/a/9/a93e4adea6158e1dd04ea5faf0dd58353a11ee1d.png)

Perhaps someone can provide a faster implementation? Hope you enjoyed these codes, perhaps you can modify them and make them more intricate/faster/better!

---

<div class="post-metadata">

**Author:** ![shenghuiy](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/shenghuiy/32/36073_2.png) [@shenghuiy](https://community.wolfram.com/u/shenghuiy)\
**Post date:** [August 22, 2019, 7:54pm UTC](https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635/2 "2019-08-22T19:54:33Z")

</div>

I worked on one interesting problem on AOPS: [https://artofproblemsolving.com/community/c4h1878869p12775512](https://artofproblemsolving.com/community/c4h1878869p12775512)

And the result turns to be Stern’s sequence (A049455, also A002487) after I have played around with Wolfram Language. This is also a strong example to show why it is necessary to do experiments in mathematics. Some simple-looking problem has connection to something rather deep and intriguing.

- `Out[9]` is the link between this problem and `Fibonacci[n]`.
- The fraction parts of `Out[8]` forms [Farey Sequence](https://en.wikipedia.org/wiki/Farey_sequence)

 ![aops2.png](https://global.discourse-cdn.com/wolfram/original/3X/3/4/346ec6c529270313d406f5076eb0f4afa29096c2.png)

[sample.nb](https://community.wolfram.com/uploads/short-url/86uUMnUVmppjFHBUX3AIQgQa8tn.nb) (92.7 KB)

---

<div class="post-metadata">

**Author:** ![sghuisman](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/sghuisman/32/27850_2.png) [@sghuisman](https://community.wolfram.com/u/sghuisman)\
**Post date:** [August 23, 2019, 9:11am UTC](https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635/3 "2019-08-23T09:11:02Z")

</div>

That’s quite remarkable that you got the sequence ‘by accident’. I can’t seem to speed up the generation of the last sequence, maybe I think about this problem the wrong way

---

<div class="post-metadata">

**Author:** ![shenghuiy](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/shenghuiy/32/36073_2.png) [@shenghuiy](https://community.wolfram.com/u/shenghuiy)\
**Post date:** [August 23, 2019, 3:58pm UTC](https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635/4 "2019-08-23T15:58:43Z")

</div>

cf = Compile[{},  
Module[{k, ok, good, n, x},  
n = 1000;  
x = Table[0, {k,n}];  
Do[k = -1;  
ok = False;  
While[! ok, k++;  
good = True;  
Do[If[x[[j]] == k, If[BitAnd[i, j] \> 0, good = False;  
Break;]], {j, 1, i - 1}];  
If[good == True, x[[i]] = k;  
Break;]], {i, 2, n}]; Return], CompilationTarget → “C”  
]

This code generates the first 1000 points in less than 0.1 seconds:

 ![4890sol.png](https://global.discourse-cdn.com/wolfram/original/3X/b/7/b7446dcd171b85935f21bc97655170b7b4d190db.png)

---

<div class="post-metadata">

**Author:** ![sghuisman](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/sghuisman/32/27850_2.png) [@sghuisman](https://community.wolfram.com/u/sghuisman)\
**Post date:** [August 26, 2019, 2:44pm UTC](https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635/5 "2019-08-26T14:44:27Z")

</div>

Thanks for your efforts!

Impressive speedup! I think both our algorithm have similar issues when it comes to scaling. Trying 4000 takes 50x longer as compared to 1000. So it seems worse than quadratic.

---

<div class="post-metadata">

**Author:** ![wolframcommunity](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/wolframcommunity/32/8335_2.png) [@wolframcommunity](https://community.wolfram.com/u/wolframcommunity)\
**Post date:** [August 26, 2019, 3:16pm UTC](https://community.wolfram.com/t/numberphile-amazing-graphs-iii/14635/6 "2019-08-26T15:16:24Z")

</div>

![2015-11-02_10-07-11.png](https://global.discourse-cdn.com/wolfram/original/3X/5/0/50e59c9ead62f729e7130d3ea1482555a75602b6.png)

- Congratulations! This post is now featured in our [Staff Pick](http://community.wolfram.com/content?curTag=staff+picks) column as distinguished by a badge on your profile of a [Featured Contributor](http://community.wolfram.com/web/sghuisman)! Thank you, keep it coming, and consider contributing your work to the [The Notebook Archive](http://notebookarchive.org)!
