In Elixir, why does my algorthm for finding prime factors go weird once it hits the number 33 and how can I fix it?

Question

I have the following module to find prime factors:

defmodule PrimeFactors do
  def factors_for(number)
      when number < 2,
      do: []

  def factors_for(number),
      do: factors_for(number, _next_attempt = 2, _accumulator = [])

  def factors_for(number, next_attempt, accumulator)
      when next_attempt > number,
      do:
        accumulator
        |> Enum.reverse()

  def factors_for(number, next_attempt, accumulator) do
    IO.inspect(label: "######## [next_attempt | accumulator]  #{[next_attempt | accumulator]}: ")
    if rem(number, next_attempt) === 0,
       do: factors_for(div(number, next_attempt), next_attempt, [next_attempt | accumulator]),
       else: factors_for(number, next_prime(next_attempt), accumulator)
  end

  defp next_prime(2),
       do: 3

  defp next_prime(n),
       do: n + 2
           |> IO.inspect(label: "######## NEXT ")

end

For most numbers, it works as expected:

For example, the output for PrimeFactors.factors_for(10200) ends with:

######## NEXT: : 17
[
  label: <<35, 35, 35, 35, 35, 35, 35, 35, 32, 91, 110, 101, 120, 116, 95, 97,
    116, 116, 101, 109, 112, 116, 32, 124, 32, 97, 99, 99, 117, 109, 117, 108,
    97, 116, 111, 114, 93, 32, 32, 17, 5, 5, 3, 2, 2, 2, 58, 32>>
]
[2, 2, 2, 3, 5, 5, 17]

But with some numbers, the output goes funky.

For example, if I do PrimeFactors.factors_for(10201), we notice when it hits next_attempt 33, the output is very unexpected:

######## NEXT: : 29
[
  label: <<35, 35, 35, 35, 35, 35, 35, 35, 32, 91, 110, 101, 120, 116, 95, 97,
    116, 116, 101, 109, 112, 116, 32, 124, 32, 97, 99, 99, 117, 109, 117, 108,
    97, 116, 111, 114, 93, 32, 32, 29, 58, 32>>
]
######## NEXT: : 31
[
  label: <<35, 35, 35, 35, 35, 35, 35, 35, 32, 91, 110, 101, 120, 116, 95, 97,
    116, 116, 101, 109, 112, 116, 32, 124, 32, 97, 99, 99, 117, 109, 117, 108,
    97, 116, 111, 114, 93, 32, 32, 31, 58, 32>>
]
######## NEXT: : 33
[label: "######## [next_attempt | accumulator]  !: "]
######## NEXT: : 35
[label: "######## [next_attempt | accumulator]  #: "]
...
######## NEXT: : 99
[label: "######## [next_attempt | accumulator]  c: "]
######## NEXT: : 101
[label: "######## [next_attempt | accumulator]  e: "]
[label: "######## [next_attempt | accumulator]  ee: "]
'ee'

Similiarly, the value goes off for PrimeFactors.factors_for(12221):

######## NEXT: : 29
[
  label: <<35, 35, 35, 35, 35, 35, 35, 35, 32, 91, 110, 101, 120, 116, 95, 97,
    116, 116, 101, 109, 112, 116, 32, 124, 32, 97, 99, 99, 117, 109, 117, 108,
    97, 116, 111, 114, 93, 32, 32, 29, 11, 11, 58, 32>>
]
######## NEXT: : 31
[
  label: <<35, 35, 35, 35, 35, 35, 35, 35, 32, 91, 110, 101, 120, 116, 95, 97,
    116, 116, 101, 109, 112, 116, 32, 124, 32, 97, 99, 99, 117, 109, 117, 108,
    97, 116, 111, 114, 93, 32, 32, 31, 11, 11, 58, 32>>
]
######## NEXT: : 33
[label: "######## [next_attempt | accumulator]  !\v\v: "]
######## NEXT: : 35
[label: "######## [next_attempt | accumulator]  #\v\v: "]
...
[label: "######## [next_attempt | accumulator]  a\v\v: "]
######## NEXT: : 99
[label: "######## [next_attempt | accumulator]  c\v\v: "]
######## NEXT: : 101
[label: "######## [next_attempt | accumulator]  e\v\v: "]
'\v\ve'

(I don't know if it is relevant, but working exercism.com's Diffie Hellman challenge, I was also noticing some strange behaviour when trying to raise to the power of 33... it seemed to throw my application into an endless loop...)

_Sidenote:_ the relevant part of this question would be `iex|1> IO.puts("#{[33 | [31,33]]}") #⇒ !^_!`. — Aleksei Matiushkin, May 02 '20 at 13:22
Actually, that is only part of the problem. But why does it start to go wrong at 33? And why is the final result `'ee'`? or `'\v\ve'`? — Brian Kessler, May 02 '20 at 13:55
_Goes wrong_ meaning exactly what? What is the expected result? What you get back? It’s impossible to understand from what you have posted. — Aleksei Matiushkin, May 02 '20 at 15:16
The factors of the input. As demonstrated above, when the input is 10200, I correctly get [2, 2, 2, 3, 5, 5, 17], but when the input is 10201, the result is 'ee' and when the input is 12221, the result is '\v\ve'. I don't know what the correct factors are offhand, but I am 100% confident they should be a list of numbers. At no time is this code using characters or strings. As you can see above, whatever is going wrong with the algorith goes wrong when it hits 33. — Brian Kessler, May 02 '20 at 16:11
`Enum.reduce('ee', &*/2) #⇒ 10201`, `Enum.reduce('\v\ve', &*/2) #⇒ 12221`. Have you at least read the answer here and the post I linked when closed this as a duplicate? `'ee' == [101, 101] #⇒ true` — Aleksei Matiushkin, May 02 '20 at 16:30
Deep enough to see how it related to the inspects, not deep enough to see how it related to the actual output of my function, which was the second and more important question which seemed ignored since someone seems to like closing questions more than they like giving direct answers. — Brian Kessler, May 02 '20 at 23:00
The actual output of your function was printed with `inspect`. The charlists basics are described in details in the very beginning of the [_Elixir_ guide](https://elixir-lang.org/getting-started/binaries-strings-and-char-lists.html#charlists). And, the last but not the least, you seem to misunderstand the purpose of SO. This is not the site created to help people who asked the question, this is a knowledge base. Nobody cares about your particular issue, people create _the knowledge base_ for future visitors, that is why it makes sense to close duplicates instead of producing similar answers. — Aleksei Matiushkin, May 03 '20 at 05:42
The output was not printed, at least not directly with inspect, but rather by executing the function in iex. It is absolutely absurd that this site should not be about helping people who actually ask questions, or to fail to recognize any nuances when determining content to be duplicates. — Brian Kessler, May 03 '20 at 07:40

score 1 · Accepted Answer · answered May 02 '20 at 13:06

1

When you interpolate a list of integers into a string, Elixir assumes the list is an "IO data", so the integers in that list are treated as char codes.

To fix this, you need to replace this line

IO.inspect(label: "######## [next_attempt | accumulator]  #{[next_attempt | accumulator]}: ")

into this line

IO.inspect([next_attempt | accumulator], label: "######## [next_attempt | accumulator]", charlists: :as_lists)

The option charlists: :as_lists forces IO.inspect to treat charlists as lists of integers.

answered May 02 '20 at 13:06

Aetherus

8,720
1
22
36

That explains _part_ of the problem. But why does it start to go wrong at 33? And why is the final result `'ee'`? or `'\v\ve'`? – Brian Kessler May 02 '20 at 13:55
1

If you check the ASCII table, you'll find that the range of printable characters is 32 (space) to 126 (~), before 32 are all "control characters". That's why your code "goes wrong" from 33. – Aetherus May 02 '20 at 22:46

In Elixir, why does my algorthm for finding prime factors go weird once it hits the number 33 and how can I fix it?

1 Answers1