Finding a digit in a specific position

  • Thread starter WWGD
  • Start date
  • #1
WWGD
Science Advisor
Gold Member
6,292
8,192
TL;DR Summary
We are given a number as a power. How to find the kth digit of a power.
Hi,
In another forum someone asked how to find the kth digit of a large prime given in the form ##2^t-1 ## , where t is a 6-digit (decimal) number. I was thinking maybe using some SQL string function , though I am not sure if input strings must be entered explicitly. Can anyone think of some other way?
 
Last edited by a moderator:

Answers and Replies

  • #2
36,251
13,308
How would SQL calculate ##2^t##? If you have the number in decimal picking the k'th element is easy.

##2^t## in binary is trivial, so you just have to convert it to decimal. There are efficient algorithms for that.
 
  • #3
pbuk
Science Advisor
Homework Helper
Gold Member
4,048
2,379
This is called a Mersenne Prime, and there are only 5 of them that satisfy the given condition with approximately 30,000 to 260,000 decimal digits.

Calculating such large integers is simple in any language with a Big Integer library, or you can download a text file from mersenne.org.

SQL is designed for a single purpose: extracting information from a relational database and would not be an appropriate choice.
 
  • #4
WWGD
Science Advisor
Gold Member
6,292
8,192
This is called a Mersenne Prime, and there are only 5 of them that satisfy the given condition with approximately 30,000 to 260,000 decimal digits.

Calculating such large integers is simple in any language with a Big Integer library, or you can download a text file from mersenne.org.

SQL is designed for a single purpose: extracting information from a relational database and would not be an appropriate choice.
I agree in general but now SQL Server includes Python ( and an ML Server) and I though maybe these could be combined to make the process more effective. But , yes, apologies to all since my post was mostly speculative with no specifics. Edit: I should have said Sql Server instead ( of just Sql), which is no longer just about Sql but it has evolved into a full data platform, including capabilities for Python, R and machine-learning. It seems all this power may be used to do current computations more effective.
 
Last edited:
  • #5
pbuk
Science Advisor
Homework Helper
Gold Member
4,048
2,379
  • #6
36,251
13,308
Why would you use SQL to call python if you can simply run python?
I don't see how SQL would do anything useful here.
 
  • #7
WWGD
Science Advisor
Gold Member
6,292
8,192
Sorry, I likely fell for the temptations of big machinery at the expense of simplicity and common sense. It's like owning a Ferrari and just using it to go to the corner store. Curious to take it out on the bahn.
 
  • #8
Baluncore
Science Advisor
12,095
6,208
In another forum someone asked how to find the kth digit of a large prime given in the form 2^t-1 , where t is a 6-digit (decimal) number.
Write t as a binary number. For 6 digits you will have about 20 bits, and 20 loops to perform later.
You need two decimal registers, each must hold at least k digits. Beyond k, the carry is irrelevant.

The first register starts at 1 and holds progressively larger powers of two. Each loop you double that register by simply adding it to itself.
The other register starts at 1, whenever a bit of t is set, the second register is multiplied by the powers register.
That requires only a k * k digit multiply.

When you have finished the set binary bits of t, subtract one.
Look at the k'th digit.
 

Suggested for: Finding a digit in a specific position

Replies
4
Views
585
Replies
5
Views
446
  • Last Post
Replies
9
Views
938
  • Last Post
Replies
1
Views
3K
Replies
23
Views
1K
Replies
1
Views
1K
Replies
1
Views
593
Replies
3
Views
149
Replies
5
Views
2K
Top