Order of factors in factorint

[m-f-h]

I thought I had seen somewhere in the documentation (maybe the "original doc" of sympy or maybe some other website) that

# factorint must give prime factors in increasing order

and I had added this as a comment somewhere in a program where it might be relevant.
But somebody reported to me that he found a counter-example:

on https://live.sympy.org/ (which also runs version 1.11.1) ... get the result in increasing order:
factorint(14152121) returns {3613:1, 3917:1}.
However, if I do list(factorint(14152121)) I get [3917, 3613]

We've checked that up to 10^8 my program returns correct results anyways,
but I wanted to have a clear answer on whether factorint is supposed to give the factors in order (possibly (only?) in some "view" of the dict's keys) or not.

Thank you in advance!

[oscarbenjamin]

I think it is unlikely that any promise about the order of the factors would have been in the docs. Since factorint returns a dict it would have always had an arbitrary order in older versions of Python since dicts were not ordered. Now dicts are ordered so there is a possibility to reorder the dict at the end but I think it is probably better just to let the caller do that if that is what they want.

Note also that sympy's printers (init_printing) might change the order:

In [9]: print(factorint(14152121))
{3917: 1, 3613: 1}

In [10]: factorint(14152121)
Out[10]: {3613: 1, 3917: 1}

In [16]: list(factorint(14152121))
Out[16]: [3917, 3613]

You can use sorted to get the factor keys in ascending order.

[m-f-h]

OK thanks. Yes of course I can use sorted(), but if the order was respected right during "production" (I can't imagine how that would not be the case during the first phase of trial factorization at least, and I'm surprised that something else would be used up to factors as small as ~1000), then I would have preferred to avoid that overhead (which at least produces an additional list, even in the best case where this list is identical to the list(dict)). So it might give a slight performace impact, esp. in cases where the relevant functions are executed hundred million times (e.g. already the 8th term for OEIS sequence a(n) = number of practical numbers up to 10^n).

PS: I find it also somewhat surprising (not to say weird) that "print()" (i.e. __str__ ?) does a worse job than the direct output of the result without print() [is that __repr__ ?].
I checked that even in the case where the result is given in the "wrong" order (decreasing primes), when I use "visual=True" it is displayed in the "correct" order (increasing primes).

[oscarbenjamin]

I would have preferred to avoid that overhead

How do you propose that factorint returns sorted factors without incurring that same overhead internally?

The current behaviour avoids the overhead for anyone who does not care about the order. I expect that the overhead is pretty small in the context of everything else that factorint does but if you want the factors to be sorted then someone needs to sort them. If factorint does it then the overhead is always incurred even when the sorted ordering is not needed.

when I use "visual=True" it is displayed in the "correct" order

That is because it uses sorted:

sympy/sympy/ntheory/factor_.py

Lines 1193 to 1205 in 68a011f

	if visual or (type(n) is dict and
	visual is not True and
	visual is not False):
	if factordict == {}:
	return S.One
	if -1 in factordict:
	factordict.pop(-1)
	args = [S.NegativeOne]
	else:
	args = []
	args.extend([Pow(*i, evaluate=False)
	for i in sorted(factordict.items())])
	return Mul(*args, evaluate=False)

Bear in mind that in previous versions of Python returning a dict explicitly meant that the ordering was arbitrary: there was no way to control the order of keys in a dict. Now there is a way to control the order but only by inserting the keys in that order. Making that work means either organising the whole routine around carefully inserting keys in a given order or otherwise sorting the keys at the end.

[m-f-h]

Thanks. I don't want to troll so I'll stop after that reply but you didn't really reply to what I wrote last. (1) It is obvious that sorted is used to display an unsorted list in order, I was surprised that __str__ didn't do it but __repr__ appears to do it, when it should IMO logically be the converse (the former being "prettyprint" and the latter being "internal representation", a priori. (2) I said I don't see how trial division could produce (<=> insert into the dict) factors in decreasing order. (3) Thus it would be natural that small factors are "automatically" inserted in order, and only when you use more complex factoring mechanisms (rho-1, elliptic curves) you may get factors in "disorder" but in that case a sorted insertion is negligible in time -- but only in that case, not for numbers with only small factors which might be the most frequent case. But OK, it's not a bug and the main thing is to be aware that the factors can not be assumed to be in order, for the moment. (PS: Yes I know that dict's keys were not in insertion order in old versions of Python. [Python2 was a really different language, with print "Hello" and range/xrange etc...] I just wondered how it would be possible that the entries be inserted in disorder, esp. for small factors, which maybe we could not notice before, but we can notice now.)
Anyway, thanks again for answering so quickly with confirmation that it is "official" that we can't rely on the order.

[oscarbenjamin]

Thus it would be natural that small factors are "automatically" inserted in order

Maybe. Again though insertion order of items into a dict was irrelevant before so the authors of the code most likely paid no attention to it. It has been less than 2 years since SymPy dropped support for Python 3.6 so it is only recently that SymPy could depend on dict order being deterministic at all.

Feel free to look at the code. Maybe it is not difficult to change it so that it naturally inserts factors in order. I'm not personally interested in this enough to look into it but there's nothing stopping you from doing so.

Possibly the reason for __repr__ to sort the keys of a dict is so that doctests would be deterministic in Python versions where dict order was not controllable e.g. this doctest would otherwise have been unreliable in older Python versions:

sympy/sympy/ntheory/factor_.py

Lines 1055 to 1056 in 68a011f

	>>> factorint(3*101**7, limit=5)
	{3: 1, 101: 7}

[sylee957]

I don't think that we need to enforce the sorting of the keys, if it is not different than users can call sorted afterwards.
Because there are algorithms that uses some nondeterminism (like ecm), there is no hope for making it build ordered dictionary efficiently.

[m-f-h]

My point was :

• IF you use ECM or similar, then the time for sorting the factors is really (!) totally (!) negligible, and
• IF you use only trial division (supposedly way further than up to p ~ 1000 only), then you do get the factors in increasing order, it can't be otherwise.
  So, in the latter case, you really have to do on purpose something very contrived, to insert the last prime divisor you find, after the last remaining (co)factor (which is necessarily larger than all factors you find earlier using trial division -- therefore that final remaining factor should obviously be inserted in the end).