Calculate greatest divisor of value in one single cell. One cell per row

[andy-andyo]

I need a formula to test a single cell to find the greatest whole number divisor of the value in the cell. The value in the cell being tested will not be a negative, fraction or any sort of decimal. My attempts so far have failed. I am using LibreOffice Calc in Linux Mint.

Example:
Row 1 - if the cell contains 4 the result is 2
Row 2 - if the cell contains 21 the result is 7
Row 3 - if the cell contains 23 the result is -1
Row 4 - if the cell contains 51 the result is 17
and so on

=IF(RC[-1]>0,MAX(IF(MOD(R[1]C[1],ROW(INDIRECT(“1:”&RC[-1])))=0,ROW(INDIRECT(“1:”&RC[-1])),-1)),"")

RC[-1] contains the value I want to find the greatest divisor of. I’ve tried to make the formula generate numbers from 1 to the value in RC[-1] using the ROW and INDIRECT functions. Then test result for divisibility using the MOD function. If a number is a divisor of RC[-1], I thought the ROW/INDIRECT functions would return the number, or otherwise -1. The MAX function would then return the maximum divisor from possible divisors.
How ever I cannot get it to work. I get #REF!. I have tried a number of things, believing that I have the context or syntax wrong -but to no avail.
It has occurred to me that I am trying to use the wrong functions, I have tried GCD but got nowhere.

Please note I am avoiding anything that uses ‘ranges’ of numbers.

Regards Andy

[mikekaganski]

Note that for any whole number, the greatest whole divisor is the number itself, so the formula can be as simple as =RC[-1]

In the absence of the smart divisibility detection algorithms, the only way I see is brute check of all whole numbers no greater than square root of the given number (a loop).

[andy-andyo]

Hi Mike
I was hoping I had corralled the “number itself” i.e. a list of primes and all numbers 1 by making it result in -1 for these. I don’t want them. The result I wished to obtain is that of my example - composite numbers only, and just the largest value of dinominator ignoring others per composite.

I was hoping that someone would see what I’m doing wrong with the syntax. I should probably try more separate steps, rather than lumping the whole thing into one formula.

Anyway I have just noticed that I copied the wrong
formula off my tryout spreadsheet as there are a couple of mistakes.
Namely R1C1 and ,"").

=IF(RC[-1]>0,MAX(IF(MOD(RC[-1],ROW(INDIRECT(“1:”&RC[-1])))=0,ROW(INDIRECT(“1:”&RC[-1])),-1)))

Any further suggestions welcome.

Regards Andy

[mikekaganski]

Hi @andy-andyo

I was hoping my was clear enough to show it’s a friendly joke, together with the more constructive second part, hinting that the real task is much more difficult, and requires a loop. See more e.g. at How to Check if a Number Is Prime (with Pictures) - wikiHow (you see: the task to check if this number is prime is equivalent to detecting the number’s greatest divisor; and the article shows that the real solution is iterative).

You can create a UDF (user-defined function) in Basic, that does the job (as said, it can find the square root of the number, then start iterating over the whole numbers from 2 up to the found square root, skipping the even ones except 2 (to save time), and checking if the number divides the argument (i.e., the remainder from the division is 0); the first found is the sought result).

function GreatestDivisor(x)
  GreatestDivisor = -1
  if (x < 4) then exit function ' Negatives, 0, 1, 2, and 3
  if (x > 2147483647) then exit function ' 2^31-1
  if (Frac(x) <> 0) then exit function

  if ((x and 1) = 0) then
    GreatestDivisor = x / 2
    exit function
  end if

  dim sq_rt
  sq_rt = Fix(Sqr(x))
  dim i
  for i = 3 to sq_rt step 2
    if ((x mod i) = 0) then
      GreatestDivisor = x / i
      exit function
    end if
  next i
end function

[JohnSUN]

@mikekaganski

…the first found is the sought result).

…and if no suitable divisor was found, then you are out of luck - you stumbled upon a prime number and this number itself will be its maximum divisor.
@mikekaganski , I would add the line GreatestDivisor = x after Dim i

[andy-andyo]

Hi Mike
Friendly joke accepted - I didn’t get it because I’m too serious (joke). I’m an artist messing about with patterns which can be described best by math. I’m aware of the prime tests. It is the Miller-Rabin test that I’m using to construct the formula I posted. I’m no genius, I’ve been having a chat with ChatGPT, a mind boggling experience, as Chatty just keeps on going with suggestions of how to build a spreadsheet formula for my spreadsheet task. Unfortunately I have had no luck with actually getting any of them to work.
Chatty has said the I should enter these formulae into the formula bar using Ctrl Shift Return. However I could not get this to work. Apparently “Range” formulas have to be entered this way.
Anyway no luck there.
Which is why I thought I was making mistakes with either syntax or the logic in the programming behind the functions, thus my understanding (nil) of how they have to be used.
Hope you don’t think I’m wasting your time. I think I have got too complex with it, but I won’t give it up yet.
Thanks for the link to the wikiHow page.
Andy

[mikekaganski]

@JohnSUN

I would add the line GreatestDivisor = x after Dim i

Indeed; but as @andy-andyo wrote,

@andy-andyo

making it result in -1 for these

[andy-andyo]

Mike
JohnSUN
Thanks for the UDF
Andy

[sokol92]

It seems to me that in this case the array formula will be very effective. Assume that cell A1 contains a positive integer less than or equal to 1048576^2.
We can start with a formula like this (enter using the key combination Ctrl + Shift + Enter):

=IF(A1<4;-1;MAX(IF(MOD(A1; ROW(X2:INDEX(X:X;SQRT(A1))))=0; A1/ROW(X2:INDEX(X:X;SQRT(A1))); -1)))

[JohnSUN]

Nice try. But for 10, 14, 22 the result of the formula will be 2 instead of 5, 7, 11

[sokol92]

@JohnSUN, the forum is educational in nature, and I suppose that, together with the author of the topic, we will write the following formulas.

[JohnSUN]

So $X$2: instead X2:?

[sokol92]

… and $X:$X.

[JohnSUN]

Now it remains to write the same thing in RC-notations and the question can be considered closed

{=IF(RC[-1]<4;-1;MAX(IF(MOD(RC[-1]; ROW(R2C:INDEX(C;SQRT(RC[-1]))))=0; RC[-1]/ROW(R2C:INDEX(C;SQRT(RC[-1]))); -1)))}

[sokol92]

@JohnSUN

question can be considered closed

My initial plans also included speeding up the formula by 4 times, discussing whether rounding is necessary for large argument values…
But it’s all up to the author of topic.

[Lupp]

I’m late once more, and I have to admit that I probably didn’t study all the previous posts thoroughly enough.

But there is one question I would like to ask the original poster:
Why do you search for the largest proper (<>1, <>TheNumber) factor contained in the number? It’s the co-factor of the smallest one. Trying a solution with the help of tests, it’s clearly adavantageous to start with small divisors, and in many cases testing will end with 2, 3, 5, or probably 7.

[mikekaganski]

@sokol92, @JohnSUN Great!

In the following form it will handle numbers up to 4398054899715:

=IFS(RC[-1]<4;-1;ISEVEN(RC[-1]);RC[-1]/2;1;MAX(IF(MOD(RC[-1];(ROW(R1C:INDEX(C;SQRT(RC[-1]/4)))*2)+1)=0;RC[-1]/(ROW(R1C:INDEX(C;SQRT(RC[-1]/4)))*2+1); -1)))

[JohnSUN]

@mikekaganski

handle numbers up to 4398054899715

Indeed! @andy-andyo , please clarify - what numbers will you be dealing with? If we know the upper limit, the maximum number, we can optimize the formula. And now we are all carried away by dividing the sample into insanely large numbers, and our formulas for large test data hang Calc for several minutes.

[andy-andyo]

ref - handle numbers up to 4398054899715
16/03/2023
hi - gradually catching up and realizing I did not answer half your questions. My spreadsheet is handling only 1000 rows at a time. Whilst in reality the numbers input into the spreadsheet will be random numbers - not in ascending or descending order - I am however testing with blocks of 1000 numbers from the Number Line that are in ascending order. I personally have no limit on the size of the numbers in the 1000 block. The computer has the limit. Andy

[JohnSUN]

@andy-andyo

handle numbers up to 4398054899715

Yes, you’re right, a computer in this sense is much weaker than a person - it is not a dreamer, it is a pragmatist. As @Lupp already pointed out, Calc can’t exactly represent a number larger than 2^53-1=9007199254740991=nine quadrillion, seven trillion, one hundred and ninety-nine billion, two hundred and fifty-four million, seven hundred and forty thousand, nine hundred and ninety-one. To simply find out if this number is not prime, you need to check its divisibility by every odd number (or each prime number) up to 94,906,265 … Quite a difficult job, but Calc can handle it - just need to come up with a not very complicated way to make him do it. For information: even if we fill the table column from beginning to end with consecutive prime numbers, all 1048576 cells, then we will only get to the number 16290047. And this is only enough to check numbers up to 265,365,631,262,209 inclusive. In other words, nine quadrillion is still a long way off. Therefore, the advice to abandon Calc and use a specialized tool seems very reasonable.

NB This very large number 2^53-1 is not prime, it is the product of three prime numbers 6361*69431*20394401