Factoring large integers

[Skip Cave]

Quora math problem:

The sum of the number of factors of a number and its square is 34. How many such numbers (<150) exist?

J solution:

+/m=.34=(b=.;fact ea n^2)+a=.;fact ea n=.1 to 100000

93

+/m=.34=(b=.;fact ea n^2)+a=.;fact ea n=.200000 to 300000

32

+/m=.34=(b=.;fact ea n^2)+a=.;fact ea n=.300000 to 400000

|limit error in fact, executing dyad q:

|a system limit was exceeded

| */>:_ q:y

Press ENTER to inspect

JVERSION

Engine: j9.6.0-beta25/j64avx2/windows

Build: commercial/2024-11-24T15:41:46/clang-18-1-8/SLEEF=1

Library: 9.6.9

Qt IDE: 2.5.3/6.5.3(6.5.3)

OS Ver: Windows 10 Version 22H2 10.0.19045

Platform: Win 64

Installer: j9.6 install

InstallPath: c:/program files/j9.6

Contact: www.jsoftware.com

Skip Cave
Cave Consulting LLC

[Skip Cave]

fact=.{{*/>:_ q:y}}

fact 3020

12

Skip Cave
Cave Consulting LLC

[Jonathan Hough]

If I understand the problem correctly, sig=: */@:>:@:(1&({ ))@:(2&p:) NB. number of factors of y (i.e. sigma function)

>: I. 34= +/"1 sig"0@(*:,])"0 >: i. 150

36 100. So the number of integers less than 150 whose sum of factors added with the sum of factors of its square is 2.

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

[Henry Rich]

If you want the factors of a number and its square, do you really need to ask for the factors of the square? 

Henry Rich

[Skip Cave]

I took the question to mean:

How many integers have the characteristic the the total number of factors in the number and its square, are equal to 34.

The statement (<150) means that there arefewer than 150 total integers that meet this criteria.

Skip Cave
Cave Consulting LLC

[Jonathan Hough]

Henry is correct. We don't need to calculate the factors of the number and its square, only one calculation will suffice.

Skip, I believe an infinite number of integers satisfy the property.
196 (2 * 7 squared) for example

In general any two distinct primes, p1 and p2, generate a number N = (p1*p2)^2
which satisfies the property, since the number of factors is going to be 9 and the number of factors of N^2 is going to
be 25. (again, I may be misunderstanding the problem).

[Ben Gorte]

Hi Skip, and others,

May I re-formulate your statement a bit? 
"How many numbers N<150 have the characteristic that when A is the number of factors in N,  and B the number of factors in N*N, then A+B = 34?"

Take, for example, 12. Its factors are 1, 2, 3, 4, 6 and 12. The factors of 12*12=144 are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72 and 144.

So that's 6+15 = 21 factors, not 34, and therefore the number 12 does not have the desired characteristic. 

Spoiler: Brute force J tells me after a minute or so, which two numbers below 150 do have it.

Ben

[Michael Day]

I've only just come across this email,  so it's probably already been dealt with,  
but here's my penn'th:  
If a number has a prime factorisation = Product(pi^qi),  the number of factors 
is Product (qi+1).  Clearly the number of factors of its square is
Product(1+2*qi),   
and we don't need to recalculate the prime factorisation of the square.
To get the qi,  it's sufficient to use _ q: ]   ,  or _&q: in my suggested function.

So letting
   nfns =: nfNandSq =:  +/@:(*/"1@:>:@(,: +:)@(_&q:))
we get: 
   +/34 = nfns"0 >:i.100000
93
   +/34 = nfns"0 range 200000 300000
32
   +/34 = nfns"0 range 300000 400000
21
It's pretty slow,  but not bad for an essentially scalar approach.  
I expect it's quicker to work through all possible prime divisors 
on the whole vector,   but that's quite a bit more programming 
effort!  Not worth it unless there's more than the one sum of 34 
to be considered. 

Cheers,

Mike

To unsubscribe from this group and stop receiving emails from it, send an email to forum+un...@jsoftware.com.

Virus-free.www.avast.com

[Don Guinn]

It's not necessary to having to square and factor large numbers to

solve this problem. Here are the first 6 solutions to this problem:

36 100 196 225 441 484

What is interesting is not their values but the number of unique

primes and how many of each prime.

q: 36 100 196 225 441 484

2 2 3 3

2 2 5 5

2 2 7 7

3 3 5 5

3 3 7 7

2 2 11 11

Any number that is the product of two pairs of any unique primes

will give a solution of 34.

What is needed is to create a verb that calculates the number

of factors for a number. First, given a prime raised to some

power p will have p+1 factors. Second, the number of ways a

set of n things can be grouped is given by !>:#n . Putting this

into a verb:

number_of_factors =: {{

'f p' =. __ q: y

*/(!<:#f),>:p

}}"0

number_of_factors 36

9

number_of_factors *:36

25

This can be put into one verb. But it is not necessary to square

the number. Simply double the number of each factor.

q:12

2 2 3

q:144

2 2 2 2 3 3

2#q:12

2 2 2 2 3 3

f_sq_f =: {{

'f p' =. __ q: y

nf =. */(!<:#f),>:p

nsqf =. */(!<:#f),>:+:p

nf+nsqf

}}"0

Here are the sums of the number of factors and its square for

a few numbers.

f_sq_f 2+i.10

5 5 8 5 13 5 11 8 13 5

Here is a list of the solutions to 2 to 100000.

list 2+I.34=f_sq_f 2+i.99998

36 100 196 225 441 484 676 1089 1156 1225

1444 1521 2116 2601 3025 3249 3364 3844 4225 4761

5476 5929 6724 7225 7396 7569 8281 8649 8836 9025

11236 12321 13225 13924 14161 14884 15129 16641 17689 17956

19881 20164 20449 21025 21316 24025 24964 25281 25921 27556

31329 31684 33489 34225 34969 37636 40401 40804 41209 42025

42436 43681 45369 45796 46225 47089 47524 47961 48841 51076

55225 56169 61009 62001 64009 64516 67081 68644 70225 71289

75076 77284 82369 84681 87025 88804 89401 90601 91204 91809

93025 95481 98596

And a list of the possible sums.

list /:~~.f_sq_f 2+i.99998

5 8 11 13 14 17 20 21

23 26 29 32 34 35 37 38

41 44 45 47 50 53 60 61

65 69 70 73 77 83 85 86

93 99 101 106 109 112 114 117

119 125 129 137 138 151 152 155

157 158 164 173 175 177 185 186

191 198 202 209 213 218 221 241

244 246 251 258 290 304 330 334

358 378 402 422 458 466 474 510

540 546 554 558 582 586 618 658

690 714 750 758 762 776 814 834

842 858 870 894 914 954 958 960

970 1012 1026 1042 1078 1170 1242 1326

1566 1698 2070 2178 2442 2574 2790 2814

3030 3186 3402 3558 3582 3882 4014 4236

4590 4626 4734 4974 4986 5238 5586 5598

5898 6066 6390 6600 10872 15144 17928 19416

23688 24984 27960 29592 32040 34824 95160 157320

[Henry Rich]

See https://code.jsoftware.com/wiki/Essays/Divisors

Henry Rich

[Mike Day]

I wondered whether anyone had seen my post;  this is 

my first sight of Don's message,  below.  (I'll deal 

separately with apparently dropouts in receipt of 

jforum messages.)

I thought I had already laboured the point that you 

need neither to use the prime factors themselves, nor to 

directly factorise the squares.  My function isn't optimal, 

but does use only the indices of the prime factors of the 

unsquared numbers,  doubling their indices to deal with 

squares.

FWIW,  my function is somewhat faster but uses more 

space than Don's.  My efforts to vectorise the task,  working 

through all relevant primes for the whole range of numbers 

produced laughably worse performance.  However,  having 

continued looking at the subject,  I've tweaked my "nfns": 

this function is a bit faster with similar space requirements:

nfnsa =: +/@:(*/@:>:@(,. +:)@(_&q:))

I wondered why Don's fn returns _ for 1;  but,  looking into the 

behaviour of both __&q:  1, as used by Don,  and _&q: 1,  as in 

nfns[a],  I'm now wondering why my fns return the "correct" 

result,  2 !

Cheers,

Mike

Sent from my iPad

On 13 May 2026, at 08:11, Henry Rich <henry...@gmail.com> wrote:

 See https://code.jsoftware.com/wiki/Essays/Divisors

Henry Rich

[Don Guinn]

Thank you Henry for politely reminding me to test before going off half-cocked on an idea. I had not seen that essay before although I should have. Such a simple and obvious solution to finding divisors.