Conjecture de Syracuse

Definition

En mathématiques, on appelle suite de Syracuse une suite d’entiers naturels définie de la manière suivante: * on part d’un nombre entier plus grand que zéro; * s’il est pair, on le divise par 2; * s’il est impair, on le multiplie par 3 et on ajoute 1. * En répétant l’opération, on obtient une suite d’entiers positifs dont chacun ne dépend que de son prédécesseur.

Par exemple, à partir de 14, on construit la suite des nombres : 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2… C’est ce qu’on appelle la suite de Syracuse du nombre 14.

\[\begin{equation} \left\{ \begin{aligned} u_0 & = N \in \mathbb{N}, \\ u_{n+1} & = \left\{ \begin{aligned} \frac{u_n}{2} & \quad \text{ if } u_n\in 2\mathbb{N}, \\ 3u_n+1 & \quad \text{ else.} \end{aligned} \right. \end{aligned} \right. \end{equation}\]

library(tidyverse)

## ── Attaching packages ────────────────────────────────────────────────────────────────────────────────────────────────── tidyverse 1.2.1 ──

## ✔ ggplot2 3.1.0     ✔ purrr   0.2.5
## ✔ tibble  1.4.2     ✔ dplyr   0.7.7
## ✔ tidyr   0.8.2     ✔ stringr 1.3.1
## ✔ readr   1.1.1     ✔ forcats 0.3.0

## ── Conflicts ───────────────────────────────────────────────────────────────────────────────────────────────────── tidyverse_conflicts() ──
## ✖ dplyr::filter() masks stats::filter()
## ✖ dplyr::lag()    masks stats::lag()

syracuse <- function(x) {
 c(x, if(x > 1) Recall(if (x %% 2) x * 3 + 1 else x / 2))
}

syracuse(6)

## [1]  6  3 10  5 16  8  4  2  1

map(7:8, syracuse)

## [[1]]
##  [1]  7 22 11 34 17 52 26 13 40 20 10  5 16  8  4  2  1
## 
## [[2]]
## [1] 8 4 2 1

Creation of data

data_syracuse <- 
  100 %>% 
  seq_len() %>% 
  tibble(N = .) %>% 
  mutate(Sequence = map(N, syracuse))

data_syracuse <-
  data_syracuse %>% 
  mutate(Length = map_int(Sequence, length),
         Max = map_dbl(Sequence, max))

–

Shortest length?

data_syracuse %>% 
  select(-Max) %>% 
  filter(Length != log2(N) + 1) %>%
  arrange(Length, desc(N))

Plots

theme_set(theme_bw())

plot_syrac <- function(data, var){
  
  var <- enquo(var)
  
  ggplot(data) +
    aes(x = N, y = !!var) +
    geom_line()
}

Unfortunately, this syntax is not supported by {ggplot2} yet. It is still in developpement.

But one can use the old syntax, which will be depreciated:

plot_syrac <- function(data, var){
    ggplot(data) +
    aes_(x = ~N, y = substitute(var)) +
    geom_line()
}

p1 <- plot_syrac(data_syracuse, Length)
p2 <- plot_syrac(data_syracuse, log10(Max)) + ylab("log(Max)")

cowplot::plot_grid(p1, p2)