{"id":345888,"date":"2023-08-12T13:04:42","date_gmt":"2023-08-12T19:04:42","guid":{"rendered":"http:\/\/tomaztsql.wordpress.com\/?p=9304"},"modified":"2023-08-12T13:04:42","modified_gmt":"2023-08-12T19:04:42","slug":"little-useless-useful-r-functions-goldbachs-conjecture-and-sieve-of-sundaram","status":"publish","type":"post","link":"https:\/\/www.r-bloggers.com\/2023\/08\/little-useless-useful-r-functions-goldbachs-conjecture-and-sieve-of-sundaram\/","title":{"rendered":"Little useless-useful R functions \u2013 Goldbach\u2019s conjecture and Sieve of Sundaram"},"content":{"rendered":"\r\n\r\n
\r\n[This article was first published on R \u2013 TomazTsql<\/a><\/strong>, and kindly contributed to R-bloggers<\/a>]. (You can report issue about the content on this page here<\/a>)\r\n
Want to share your content on R-bloggers? click here<\/a> if you have a blog, or here<\/a> if you don't.\r\n<\/div>\n\n

This is fun \"\ud83d\ude42\" It is also O(MAX) complexity. But first some background. Since the problem is super old, we are not intending to solve it, merely to play with it. In the number theory of mathematics, the Goldbach\u2019s conjecture states that for every even integer<\/strong> (greater than 2) can be expressed with the sum of two prime numbers. There are also far cries from this theory. For example, prove that every even number can be written as the sum of not more than 300.000 primes (by Schnirelman (1939)).<\/p>\n\n\n\n

To put this to test, we created a simple Prime function, to determine if integer is a prime or not.<\/p>\n\n\n

\n\n# sieve of sundaram\nsieve_of_sundaram <- function(limit) {\n  n <- (limit - 1) %\/% 2\n  sieve <- rep(TRUE, n + 1)\n  \n  for (i in 1:n) {\n    j <- 1\n    while (i+j+2*i*j <= n) {\n      sieve[i+j+2*i*j] <- FALSE\n      j <- j + 1\n    }\n  }\n  primes <- c(2,(2*(1:n)+1)[sieve])\n  return(primes)\n}\n\n# is prime\nis_prime <- function(n) {\n  if (n <= 1)  return(FALSE)\n  if (n <= 3)  return(TRUE)\n  if (n %% 2 == 0 || n %% 3 == 0) return(FALSE)\n  i <- 5\n  while (i*i <= n) {\n    if (n %% i == 0 || n %% (i + 2) == 0) return(FALSE)\n    i <- i + 6\n  }\n  return(TRUE)\n}\n  \n<\/pre>\n\n\n
For fun, I am adding the famous Sieve of Sundaram algorithm for finding multiple primes in an array of integers.<\/p>\n\n\n\n
For the next step, we find sum of all two primes for every even number as input; with other words, the Goldbach\u2019s conjecture.<\/p>\n\n\n
\ngoldbach_conjecture <- function(even_num) {\n  if (even_num <= 2 || even_num %% 2 != 0) {\n    return("Number must be even and greater than 2.")\n  }\n  c <- NULL\n  for (i in 2:(even_num \/ 2)) {\n    if (is_prime(i) && is_prime(even_num - i)) {\n      #cat("Goldbach's pairs for", even_num, "are:", i, "+", even_num - i, "\\n")\n      c <- cbind(c,i) # nof solutions\n    } \n  }\n  return(length(c))\n}\n\n<\/pre>\n\n\n
But not to end here, let\u2019s put the Goldbach\u2019s conjecture to test and see how the solutions are generated:<\/p>\n\n\n
\n#make some 1000 solutions\nsol <- NULL\nfor (i in seq(4,1000, by=2)){\n  nof_solutions <- goldbach_conjecture(i)\n  sol <- rbind(sol, data.frame(n=i, nof=nof_solutions))\n}\n\n# plot solutions; alternating solutions\nplot(sol$n, sol$nof, type = "p", xlab = "Even number", ylab = "Number of Solutions", main = "Goldbach's Conjecture") \nreg<-lm(nof ~ n, data = sol)\nabline(reg, col="red")\n<\/pre>\n\n
\n
\"\"<\/a><\/figure><\/div>\n\n\n
We see the \u201calternating\u201d pattern of solutions for every even number between 4 and 1000 as sum of two primes.<\/p>\n\n\n\n
And the distribution of prime frequencies is equally \u201cinteresting\u201d \"\ud83d\ude42\"<\/p>\n\n\n
\n
\"\"<\/a><\/figure><\/div>\n\n\n
As always, code is available on Github in \u00a0Useless_R_function repository<\/a>. The sample file in this repository is\u00a0here<\/a>\u00a0(filename:\u00a0Goldbach_conjecture.R<\/em>) Check the repository for future updates.<\/p>\n\n\n\n
Happy R-coding and stay healthy!<\/p>\n\n
\r\n
To leave a comment<\/strong> for the author, please follow the link and comment on their blog:  R \u2013 TomazTsql<\/a><\/strong>.<\/div>\r\n
\r\nR-bloggers.com<\/a> offers daily e-mail updates<\/a><\/strong> about R<\/a> news and tutorials about learning R<\/a> and many other topics. Click here if you're looking to post or find an R\/data-science job<\/a>.\r\n\r\n
Want to share your content on R-bloggers? click here<\/a> if you have a blog, or  here<\/a> if you don't.\r\n<\/div>","protected":false},"excerpt":{"rendered":"
 This is fun \ud83d\ude42 It is also O(MAX) complexity. But first some background. Since the problem is super old, we are not intending to solve it, merely to play with it. In the number theory of mathematics, the Goldbach\u2019s conjecture\u2026Read more \u203a<\/div>\n
<\/div>\n
<\/div>\n","protected":false},"author":1281,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[],"aioseo_notices":[],"jetpack-related-posts":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/posts\/345888"}],"collection":[{"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/users\/1281"}],"replies":[{"embeddable":true,"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/comments?post=345888"}],"version-history":[{"count":23,"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/posts\/345888\/revisions"}],"predecessor-version":[{"id":383346,"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/posts\/345888\/revisions\/383346"}],"wp:attachment":[{"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/media?parent=345888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/categories?post=345888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.r-bloggers.com\/wp-json\/wp\/v2\/tags?post=345888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}