Construct Big Integers with odd digits only

New to Julia
,
1

My question is essentially: what is the best way to solve this problem with Julia? I don’t think I have the “right words” or “concepts” to even research a solution.

The Problem:

Say I wanted to construct positive integers with the odd digits only: 1,3,5,7,9

Big integers, 40 or more digits:
397,573,713,333,795,317,993,317,997,357,997,395,179,335 [42 digits]

They eventually have to be converted to BigInt type.

I need to be able to increment them upwards to the next value.

However, for this question let’s use 3 digit numbers.

When I first looked at this, I figured this could be a good use of iterators. We have 3 number positions (little-endian notation)

[3][2][1]

Spin up 3 iterators that cycle 1,3,5,7,9 and concatenate them together.

However, if you do that and use zip() to run them, all the iterators run at the same time and you get:

111
333
555
777
999

What is needed is iterator1 to complete a cycle, then trigger iteraror2 to advance 1. Then iterator1 does another cycle. Like normal counting, but you’re only using odd digits.

Now I’ll want to start at some large number (see above). I figure I could just specify different iterator staring positions for each digit position. In the three digit example iterrator3 could be specified as 5,7,9,1,3; iterator2 as 3,5,7,9,1; and iterator1 as 1,3,5,7,9. The starting number would then be 531. That is, of course, if the iterator idea worked, of course.

So I looked around. Maybe “iterator” wasn’t the concept I needed.

Permutations?

julia> using Combinatorics

julia> p3=permutations(1:2:9,3)
Combinatorics.Permutations{StepRange{Int64, Int64}}(1:2:9, 3)

julia> collect(p3)
60-element Vector{Vector{Int64}}:
 [1, 3, 5]
 [1, 3, 7]
 [1, 3, 9]
 [1, 5, 3]
 [1, 5, 7]
 [1, 5, 9]
 [1, 7, 3]
 [1, 7, 5]
 [1, 7, 9]
 [1, 9, 3]
 [1, 9, 5]
 [1, 9, 7]
 ⋮
 [9, 1, 5]
 [9, 1, 7]
 [9, 3, 1]
 [9, 3, 5]
 [9, 3, 7]
 [9, 5, 1]
 [9, 5, 3]
 [9, 5, 7]
 [9, 7, 1]
 [9, 7, 3]
 [9, 7, 5]

Only got 60 permutations (expected 125); not clear how one would start it at a specific number.

Subsets?

julia> using IterTools
julia> s3=subsets(1:2:9,3)
IterTools.Binomial{StepRange{Int64, Int64}}(1:2:9, 5, 3)

julia> c3=collect(s3)
10-element Vector{Vector{Int64}}:
 [1, 3, 5]
 [1, 3, 7]
 [1, 3, 9]
 [1, 5, 7]
 [1, 5, 9]
 [1, 7, 9]
 [3, 5, 7]
 [3, 5, 9]
 [3, 7, 9]
 [5, 7, 9]

Only got 10 elements; not clear how to start at specific number.

2

This generates 125 vectors from 1:2:9:

julia> [[x, y, z] for x ∈ 1:2:9, y ∈ 1:2:9, z ∈ 1:2:9]
5×5×5 Array{Vector{Int64}, 3}:
[:, :, 1] =
 [1, 1, 1]  [1, 3, 1]  [1, 5, 1]  [1, 7, 1]  [1, 9, 1]
 [3, 1, 1]  [3, 3, 1]  [3, 5, 1]  [3, 7, 1]  [3, 9, 1]
 [5, 1, 1]  [5, 3, 1]  [5, 5, 1]  [5, 7, 1]  [5, 9, 1]
 [7, 1, 1]  [7, 3, 1]  [7, 5, 1]  [7, 7, 1]  [7, 9, 1]
 [9, 1, 1]  [9, 3, 1]  [9, 5, 1]  [9, 7, 1]  [9, 9, 1]

[:, :, 2] =
 [1, 1, 3]  [1, 3, 3]  [1, 5, 3]  [1, 7, 3]  [1, 9, 3]
 [3, 1, 3]  [3, 3, 3]  [3, 5, 3]  [3, 7, 3]  [3, 9, 3]
 [5, 1, 3]  [5, 3, 3]  [5, 5, 3]  [5, 7, 3]  [5, 9, 3]
 [7, 1, 3]  [7, 3, 3]  [7, 5, 3]  [7, 7, 3]  [7, 9, 3]
 [9, 1, 3]  [9, 3, 3]  [9, 5, 3]  [9, 7, 3]  [9, 9, 3]

(...)

[:, :, 5] =
 [1, 1, 9]  [1, 3, 9]  [1, 5, 9]  [1, 7, 9]  [1, 9, 9]
 [3, 1, 9]  [3, 3, 9]  [3, 5, 9]  [3, 7, 9]  [3, 9, 9]
 [5, 1, 9]  [5, 3, 9]  [5, 5, 9]  [5, 7, 9]  [5, 9, 9]
 [7, 1, 9]  [7, 3, 9]  [7, 5, 9]  [7, 7, 9]  [7, 9, 9]
 [9, 1, 9]  [9, 3, 9]  [9, 5, 9]  [9, 7, 9]  [9, 9, 9]
3

I’m not a 100% sure I understood what you are trying, but here’s a way to increment a number in a odd-digit way:

function incr2!(v::AbstractVector{Int})
    for i in reverse(eachindex(v))
        v[i] = mod1(v[i]+2, 10)
        if v[i] != 1
            break
        end
    end
    return v
end

julia> v = MVector(1,7,5)
3-element MVector{3, Int64} with indices SOneTo(3):
 1
 7
 5

julia> incr2!(v)
3-element MVector{3, Int64} with indices SOneTo(3):
 1
 7
 7

julia> incr2!(v)
3-element MVector{3, Int64} with indices SOneTo(3):
 1
 7
 9

julia> incr2!(v)
3-element MVector{3, Int64} with indices SOneTo(3):
 1
 9
 1
1 Like
4

You can also think about your numbers as being numbers in a base 5 system but where the digits are not 0 1 2 3 4 but 1 3 5 7 9

N=3
for i=0:5^N-1
    thevalue=evalpoly(10,2 .*digits(i,base=5,pad=N) .+1)
   @show thevalue
end
4 Likes
5

Hey, that works pretty nice!

I can also change the return of the function to return the BigInt:

    function incr2!(v::AbstractVector{Int})
        for i in reverse(eachindex(v))
            v[i] = mod1(v[i]+2, 10)
            if v[i] != 1
                break
            end
        end
        return parse(BigInt, join(string.(v)))
    end

then running it:

Julia> v=MVector(1,9,9,7,9,9,7,7,7,5,3,3,9,9,7,1,5,5,9,3,5,7,5,1,7,9,3,3,5,3,5,1,3,7)
julia> v=MVector(1,9,9,7,9,9,7,7,7,5,3,3,9,9,7,1,5,5,9,3,5,7,5,1,7,9,3,3,5,3,5,1,3,7)
34-element MVector{34, Int64} with indices SOneTo(34):
 1
 9
 9
[truncated]

julia> incr2!(v)
1997997775339971559357517933535139

julia> incr2!(v)
1997997775339971559357517933535151

julia> incr2!(v)
1997997775339971559357517933535153

julia> incr2!(v)
1997997775339971559357517933535155

julia> incr2!(v)
1997997775339971559357517933535157

julia> incr2!(v)
1997997775339971559357517933535159

julia> incr2!(v)
1997997775339971559357517933535171

julia> incr2!(v)
1997997775339971559357517933535173

julia> incr2!(v)
1997997775339971559357517933535175
6

I was going to say that you can do

parse(BigInt, join(v))

instead, but, oddly, join(v) is slower than join(string.(v)).