# Naive Grouping for Factorization

UPDATE: I have posted this question on math.se along with the identification of a new relationship to lattice points on hyperbola.

I have a naive grouping method for factorization. I am curious as to its novelty and aspects of the code below that will increase its efficiency.

The method is best described with an example:

For $n = 798,607$ if we start with a seed group of $59$, we would have $17$ groups of $13,535$ and $42$ groups of $13,536$. Neither the $17$ nor the $42$ will evenly parse the other grouping totals so we double the seed group. Now we have $118$ groups in total, $17$ groups of $6,767$ and $101$ groups of $6,768$. The $6,767$ can be distributed among the $101$ groups, resulting in factors of $101$ groups of $7,907$.

I have found that all seed groups are odd and less than $\sqrt n \over 2$ and there exist multiple (unknown quantity) seed groups yielding factors. The seed groups ($i$) are only expanded until the groups are greater than the group counts, or the initial seed group splits do not carry forward (i.e., $17$ or $42$ groups from seed group $59$ needs to be a solution in the $118$ groups split.)

#Naive Grouping
NaiveGrouping <- function(number){

r<- as.integer(sqrt(number)/2)

for (i in seq(3,r,2)){
for (j in 0:(floor(log2(number)))){

Seed_Group<-(i*(2^j))

Counts <- (number/Seed_Group)

if(Counts%%1==0){
return(c(Seed_Group=Seed_Group,End_Group=Seed_Group,Factors=Seed_Group,number/Seed_Group))
}

count_ceiling <- (ceiling(Counts))
count_floor <- (floor(Counts))

initial_group_ceiling <- (number%%i)
initial_group_floor <- (i - number%%i)

group_ceiling <- number%%Seed_Group
group_floor <- (Seed_Group - (group_ceiling))

if(group_floor==initial_group_floor | group_ceiling==initial_group_ceiling)
if(group_floor==1 | group_ceiling==1) next
if(group_floor>count_ceiling | group_ceiling>count_floor) break

if(count_floor%%group_ceiling==0){
return(matrix(c(group_floor,count_floor,group_ceiling,count_ceiling,i,group_floor+group_ceiling,group_ceiling,number/group_ceiling),4,2,byrow=TRUE,dimnames=list(c("Group Floor","Group Ceiling", "Seed Group, End Group","Factors"),c("Groups","Counts"))))

}

if(count_ceiling%%group_floor==0){
return(matrix(c(group_floor,count_floor,group_ceiling,count_ceiling,i,group_floor+group_ceiling,group_floor,number/group_floor),4,2,byrow=TRUE,dimnames=list(c("Group Floor","Group Ceiling", "Seed Group, End Group","Factors"),c("Groups","Counts"))))

}
}

}
return("Prime")
}

• Is there a specific concern about code efficiency? You could for example show us what you have tested that was too slow for your taste. – flodel Mar 15 '15 at 23:29
• NaiveGrouping(23) throws an error. NaiveGrouping(40) returns nothing. NaiveGrouping(50) returns a matrix. NaiveGrouping(51) returns a vector. It is recommended that a function returns the same type of output regardless of the (valid) input. – flodel Mar 15 '15 at 23:39
• Comparing with your other algorithm (codereview.stackexchange.com/questions/83997/…), isn't the goal similar? I.e., for an input n, find two p and q such that n == p * q? If so, would it make sense for the output to just be a vector of two integers? – flodel Mar 15 '15 at 23:45
• Thanks flodel, this algorithm has a reduced search space vs. the trial multiplication method. It is deterministic in half the space, with an unknown amount of other seed groups. So in essence, we are trying to find multiple needles in a smaller haystack instead of the fast checking of the multiplication method. I think your suggestion of eliminating the sequence with an increment of the current value may yield substantial benefits. My benchmark with this method was against Pollard's rho and avoiding all of the gcd calculations with smaller modulus calculations. – Fred Viole Mar 15 '15 at 23:53
• Also, if you start with group 2 instead of 3 all even numbers (40) will be captured. I started with 3 because I am after the semiprime numbers. The vector output (51) is because the seed group is the factor (3). (23) is prime and it will not output a vector or matrix. The output can be reduced to a vector, but I was demonstrating how the progression of seed groups yields a factor. – Fred Viole Mar 16 '15 at 0:02