# Construct Big Integers with odd digits only

**URL:** <https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927>\
**Category:** New to Julia\
**Tags:** question, iterators\
**Created:** [September 8, 2022, 8:28am UTC](https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927 "2022-09-08T08:28:36Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![blackeneth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blackeneth/32/10353_2.png) [@blackeneth](https://discourse.julialang.org/u/blackeneth)\
**Post date:** [September 8, 2022, 8:28am UTC](https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927/1 "2022-09-08T08:28:36Z")

</div>

**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
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
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.

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [September 8, 2022, 8:34am UTC](https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927/2 "2022-09-08T08:34:35Z")

</div>

This generates 125 vectors from `1:2:9`:

```julia
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]

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 8, 2022, 9:05am UTC](https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927/3 "2022-09-08T09:05:37Z")

</div>

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:

```julia
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
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

```

---

<div class="post-metadata">

**Author:** ![JM\_Beckers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jm_beckers/32/22482_2.png) [@JM\_Beckers](https://discourse.julialang.org/u/JM_Beckers)\
**Post date:** [September 8, 2022, 9:13am UTC](https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927/4 "2022-09-08T09:13:52Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![blackeneth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blackeneth/32/10353_2.png) [@blackeneth](https://discourse.julialang.org/u/blackeneth)\
**Post date:** [September 8, 2022, 9:55am UTC](https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927/5 "2022-09-08T09:55:41Z")

</div>

Hey, that works pretty nice!

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

```julia
    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
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

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [September 8, 2022, 10:29am UTC](https://discourse.julialang.org/t/construct-big-integers-with-odd-digits-only/86927/6 "2022-09-08T10:29:08Z")

</div>

> [@blackeneth](#):
>
> `parse(BigInt, join(string.(v)))`

I was going to say that you can do

```julia
parse(BigInt, join(v))

```

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