Skip to content

Instantly share code, notes, and snippets.

@mmahmoudian
Last active December 16, 2019 13:56
Show Gist options
  • Save mmahmoudian/32dbd85442e74e93b733d4fe48beda1e to your computer and use it in GitHub Desktop.
Save mmahmoudian/32dbd85442e74e93b733d4fe48beda1e to your computer and use it in GitHub Desktop.
if you treat the number as a string and break it at some point(s), the square of sums should be equal to the number.
################################################################################
## This code is in response to the following tweet of "Fermat's Library" ##
## https://twitter.com/fermatslibrary/status/1180837639915819008?s=20 ##
## ##
## It is also corresponsing to the following entry in the On-Line ##
## Encyclopedia of Integer Sequences (OEIS): ##
## https://oeis.org/search?q=A104113 ##
## ##
## Author: Mehrad Mahmoudian ##
## License: GPL3 ##
## ##
## Description: ##
## The in the aforementioned tweet it is mentioned that 81 is the only ##
## number that has (8+1)^2=81 feature. I thought it is a nice morning ##
## coding challenge. From that tweet either of these conditions can be ##
## deduced: ##
## - if you treat the number as a string and cut it in half, the square ##
## of sums should be equal to the number. ##
## - if you treat the number as a string and split it into individual ##
## digits, the square of sums should be equal to the number ##
## - if you treat the number as a string and break it at some point(s), ##
## the square of sums should be equal to the number. ##
## ##
## I realized the last one is the most complex one and also it contains the ##
## other two in itself, so I challenged myself :D ##
################################################################################
#-------[ load packages ]-------#
{
library("parallel")
library("foreach")
library("doParallel")
}
#-------[ initial settings ]-------#
{
## what range of numbers should it cover
lower_bound <- 10
upper_bound <- 100000000
# how many tasks should we push to each CPU core (this depends on the processing
# power of each core and the total available memory, so don't set it too high
jumps <- 250
setwd("~/tmp/A104113/")
}
#-------[ internal functions ]-------#
{
func_cutter <- function(x, cuts){
## Description:
## A function to cut a string at given points
##
## Arguments:
## x: A character vector of length 1
## cuts: a numeric vector of length smaller than nchar(x)
# create a collective variable
final <- c()
# go through all the cutting points that is provided to the function
for(i in seq_along(cuts)){
# if the index is 1
if(i == 1){
# append the first few chracters as an item to the collective vector
final <- c(final, substr(x = x, start = 1, stop = cuts[i]))
}
# if we got to the end of the cutting points list
if(i == length(cuts)){
# set the ending to be the end of the string
tmp_end_index <- nchar(x)
}else{
# using the next cutting point as the ending position
tmp_end_index <- cuts[i+1]
}
final <- c(final, substr(x = x, start = cuts[i]+1, stop = tmp_end_index))
}
return(final)
}
chunk2 <- function(x,n){
## source: https://stackoverflow.com/a/16275428/1613005
##
## Description:
## A function to break the provided vector into n equal smaller vectors
##
## Arguments:
## x: a vector that you want to cut into chunks
## n: number of chunks
split(x,
cut(seq_along(x),
n,
labels = FALSE))
}
}
#-------[ ininital setup ]-------#
{
# set the number to maximum possible but leave one out for the grace
parallel.cores <- parallel::detectCores() - 1
## register parallel backend
cl <- parallel::makeCluster(parallel.cores, outfile = "")
doParallel::registerDoParallel(cl)
}
#-------[ main ]-------#
{
# create an empty vector to be filled in the loop below
final <- c()
# initiate the start of i in the loop
i_low <- lower_bound
## initiate the result file with a separator tagged with date and time
header_txt <- paste0("[ ", format(Sys.time(), "%Y%m%d-%H%M%S"), " ]")
padding_length <- (80 - nchar(header_txt)) / 2
header_txt <- paste0(paste(rep.int("-", ceiling(padding_length)), collapse = ""),
header_txt,
paste(rep.int("-", floor(padding_length)), collapse = ""))
cat(header_txt, file = "result.txt", sep = "\n", append = T)
# run as long i is less than the upper bound
while(i_low <= upper_bound){
# define how high we want to go in this round of while
i_high <- i_low + (parallel.cores * jumps)
# if the hight we defined is larger than the user-defined upper bound
if(i_high > (upper_bound + 1)){
# trim it to be as high as upper bound +1 (+1 is to make the while loop break)
i_high <- upper_bound + 1
}
# break the distance between i_low to i_high to equal chunks where chunk count is equal to parallel.cores
chunks <- chunk2(i_low:i_high, parallel.cores)
cat(i_low, ":", i_high, ":: ")
# got through the numbers between the lower and upper limits of this round of while
tmp_final <- foreach(ii = chunks,
.inorder = TRUE,
.combine = c) %dopar% {
tmp_outer_collective <- c()
for(i in ii){
tmp_inner_collective <- c()
# iterate through the possible number of cuts we can have to the string
for(j in seq_len(nchar(i) - 1)){
# generate all possible combination of cutting positions considering the
# constraint on total number of cuts allowed
combinations <- apply(combn(x = nchar(i) - 1, m = j), 2, function(a){
func_cutter(x = i, cuts = a)
})
# go through all generated pieces and do the math
for(k in 1:ncol(combinations)){
# select this specific combination
x <- as.character(combinations[, k])
# turn this combination into numbers
x_numeric <- as.numeric(x)
# if the square of sums was equal to the number we are testing
if((sum(x_numeric)^2) == i){
tmp_success <- paste0("(", paste0(x, collapse = "+"), ")^2")
tmp_inner_collective <- c(tmp_inner_collective, tmp_success)
}
}
}
# if the collective variable was not empty
if(length(tmp_inner_collective)){
# retusn a character vector of length 1 with correct desired format
tmp_inner_collective <- paste0(paste0("[",
format(Sys.time(),
"%Y%m%d-%H%M%S"),
"]\t"),
i,
"\t::\t",
paste(tmp_inner_collective,
collapse = ", "))
}else{
tmp_inner_collective <- NULL
}
tmp_outer_collective <- c(tmp_outer_collective, tmp_inner_collective)
}
return(tmp_outer_collective)
}
# append to the global collective1 variable
final <- c(final, tmp_final)
if(!is.null(tmp_final)){
cat(length(tmp_final), "\n")
cat(tmp_final, file = "result.txt", sep = "\n", append = T)
}else{
cat("0\n")
}
# put the highest I we covered to be the lowest to get ready for the next round of while loop
i_low <- i_high
invisible(gc())
}
parallel::stopCluster(cl)
invisible(gc())
}
#-------[ save the results ]-------#
{
comment(final) <- paste("From", lower_bound, "to", upper_bound)
saveRDS(object = final,
file = paste0(paste(format(Sys.time(), "%Y%m%d-%H%M%S"), "final", lower_bound, "to", upper_bound, sep = "_"), ".RDS"))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment